As you may know using KMP to pre-calculate the longest length `L`

of proper prefix which is also a suffix costs O(n) time and O(n) space, and the answer for this problem will simply be `L && n%(n-L)==0`

.

Without using KMP, we can implement a more straightforward algorithm with a little more time spending. As many has posted the solution to check whether `s`

has a proper prefix which is also a suffix with length `L`

such that `n%(n-L)==0`

simply using straightforward string comparison.

```
bool repeatedSubstringPattern(string s) {
for (int i = 1, n = s.size(), sqt = sqrt(n); i <= sqt; ++i)
if (n%i == 0)
for (int L : {n-i, n-n/i})
// O(n) space or char-wise comparison for O(1) space
if (L && s.substr(n-L) == s.substr(0, L)) return true;
return false;
}
```

The interesting question is what is the "**a little more**" time spending? The loop index `i`

goes up to `sqrt(n)`

to check substrings of length `n-n%i`

only for `n%i==0`

, so the time complexity will be

- O(√n + Σ
_{d|n}(n-d)) ≤ O(√n + Σ_{d|n}n) = O(nd(n))

where d(n) is the divisor function of n (number of divisors). So we got the **upper asymptotic bound**.

For **lower asymptotic bound**, note that any proper divisor d ≤ n/2, so

- O(√n + Σ
_{d|n}(n-d)) ≥ O(Σ_{d|n}n/2) = O(nd(n)).

Function d(n) has **upper asymptotic bound** O(n^{1/loglog(n)}), so the overall time complexity of the problem is

- O(n
^{1+1/loglog(n)}) or o(n^{1+e}) for any small e > 0,

which means even though the KMP-less method is slower than KMP, but it is just ** infinitely tiny** slower for worst case :-)