Finding if a string is an iterative substring?
- by EsotericMe
I have a string S. How can I find if the string follows S = nT.
Examples:
Function should return true if
1) S = "abab"
2) S = "abcdabcd"
3) S = "abcabcabc"
4) S = "zzxzzxzzx"
But if S="abcb" returns false.
I though maybe we can repeatedly call KMP on substrings of S and then decide.
eg: for "abab": call on KMP on "a". it returns 2(two instances). now 2*len("a")!=len(s)
call on KMP on "ab". it returns 2. now 2*len("ab")==len(s) so return true
Can you suggest any better algorithms?