# 1-line C++ solution: return (s+s).find(s,1) < s.size() with proof!

• ``````    bool repeatedSubstringPattern(string& s) { return (s+s).find(s,1) < s.size(); }
``````

Since neither `string::find` nor `std::strstr` specify complexity, the algorithm is up to whatever their implementation is. (e.g., `O(N)` time and space if using KMP, where `N = s.size()`)

Why condition `return (s+s).find(s,1) < s.size()` is equivalent to substring repetition?
Proof: Let `N = s.size()` and `L := (s+s).find(s,1)`, actually we can prove that the following 2 statements are equivalent:

1. `0 < L < N`;
2. `N%L == 0` and `s[i] == s[i%L]` is true for any `i` in `[0, N)`. (which means `s.substr(0,L)` is the repetitive substring)

Consider function `char f(int i) { return s[i%N]; }`, obviously it has a period `N`.

"1 => 2": From condition 1, we have for any `i` in `[0,N)`

• `s[i] == (s+s)[i+L] == s[(i+L)%N]`,
which means `L` is also a positive period of function `f`. Note that `N == L*(N/L)+N%L`, so we have
• `f(i) == f(i+N) == f(i+L*(N/L)+N%L) == f(i+N%L)`,
which means `N%L` is also a period of `f`. Note that `N%L < L` but `L := (s+s).find(s,1)` is the minimum positive period of function `f`, so we must have `N%L == 0`. Note that `i == L*(i/L)+i%L`, so we have
• `s[i] == f(i) == f(L*(i/L)+i%L) == f(i%L) == s[i%L]`,
so condition 2 is obtained.

"2=>1": If condition 2 holds, for any `i` in `[0,N)`, note that `N%L == 0`, we have

• `(s+s)[i+L] == s[(i+L)%N] == s[((i+L)%N)%L] == s[(i+L)%L] == s[i]`,
which means `(s+s).substr(L,N) == s`, so condition 1 is obtained.

• It can be even faster.

``````class Solution {
public:
bool repeatedSubstringPattern(string s) {
return (s + s.substr(0, s.size() / 2)).find(s, 1)!= string::npos;
}
};
``````

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