# C++ O(n) using KMP, 32ms, 8 lines of code with brief explanation.

• First, we build the KMP table.

1. Roughly speaking, dp[i+1] stores the maximum number of characters that the string is repeating itself up to position i.
2. Therefore, if a string repeats a length 5 substring 4 times, then the last entry would be of value 15.
3. To check if the string is repeating itself, we just need the last entry to be non-zero and str.size() to divide (str.size()-last entry).
``````    bool repeatedSubstringPattern(string str) {
int i = 1, j = 0, n = str.size();
vector<int> dp(n+1,0);
while( i < str.size() ){
if( str[i] == str[j] ) dp[++i]=++j;
else if( j == 0 ) i++;
else j = dp[j];
}
return dp[n]&&dp[n]%(n-dp[n])==0;
}
``````

• Same implementation.

My p[i] stands for longest common string length of prefix string and the string ended with position i.

The important point is the last one: `len % (len - p[len - 1]) == 0`

for a string like below, if p[len-1] = 15, len=20:

`#####~~~~~^^^^^`\$\$\$\$\$
#####`~~~~~^^^^^\$\$\$\$\$`

by p[len-1] = 15, we know the strings colored red are the same.

so you can infer that:

`##### == ~~~~~`

`~~~~~ == ^^^^^`

`^^^^^ == \$\$\$\$\$`

The whole is repeating as `#####`

the length of it is 5, which can be completely divided by len.

That's how this final condition works.

``````bool repeatedSubstringPattern(string str) {
int len = str.length(), i = 0, j = 1;
int p[len];
while (j < len)
if (str[i] == str[j])
p[j++] = ++i;
else {
if (!i)
p[j++] = 0;
else
i = p[i - 1];
}
return p[len - 1] && len % (len - p[len - 1]) == 0;
}
``````

• really wonderful idea!!!

• Same idea but more Simple version

``````public:
bool repeatedSubstringPattern(string str) {
int k = -1, m = str.size(), pi[m+1] = {-1};
for(int i=1; i <= m; i++){
while(k>=0 && str[k]!=str[i-1]) k = pi[k];
pi[i] = ++k;
}
return pi[m]&&(pi[m]%(m-pi[m])==0);
}
};
``````

• @jade86 - in your solution, shouldnt you return false at the point of first mismatch after you have a non-zero value of j, .... i.e. at the line
-->else j=dp[j];

• len % (len - p[len - 1]) == 0;

What I agree is that:
if len % (len - p[len - 1]) == 0, then the pattern is repeated.

However, if len % (len - p[len - 1]) != 0, can we lead to the conclusion that pattern is not repeated? Do we need to recursively check p[p[len - 1] - 1] and so on?

In other words, I agree that len % (len - p[len - 1]) == 0 is a sufficient condition for the statement that pattern is repeated, but may not be a necessary condition.

Any comment on it? Thx.

• @tobe4321 I think you can try the case "abaaba"

• @Zhen_Li p[n] means the substr(0, p[n]) is the same with the substr(n - p[n], p[n]). Assume x = len / (len - p[len - 1]), y = len % (len - p[len - 1]), we must have x*(len - p[len - 1]) + y = len. If y != 0, since y < len - p[len-1], it's definitely not a repeated substring.

• Brilliant code & solution!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.