Finding if a string is an iterative substring?
Posted
by
EsotericMe
on Stack Overflow
See other posts from Stack Overflow
or by EsotericMe
Published on 2011-01-14T22:45:59Z
Indexed on
2011/01/14
23:53 UTC
Read the original article
Hit count: 177
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?
© Stack Overflow or respective owner