@zzg_zzm Thanks for your reply. But I thought it still not solve the problem, that is to say I can't obviously see how first match leads to minimum?
Instead define T as any positive period of f, I think the right logic should be
L is the first match position, L <= T, T is the minimum period of f
Because f is period of L(from your original proof), L >= T
=> L == T
Forgive my verbosity.
@yaopiupiupiu Yeah, I think your are right. I think I forgot the inner loop, but substr won't make difference here, as the comparison takes also linear time. I believe it is actually O(Number_of_divisors * Length_of_string) which is bounded by O(n^1.5), which seems cumbersome.
What's more, so far, I can not see how to reduce this complexity but it seems to me that it's kind of huge. I would be glad to hear if there is any idea to improve it!
Nice solution, clear and neat code and runs very fast. I think the time complexity should be O(n^4), where n is the length of s. The outer loop plus find prefix contributes n^2, while the mem map will store up to all potential substrings of s, which contributes n^2, so the final time complexity should be O(n^4)
How did you get O(n^3)? Your for loop recursive function looks worse than n!. Just imagine a large n, you break that up in every partition and then do another recursive call for each part. (1,n-1),(2,n-2)...etc