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: 156

Filed under:
|
|

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

Related posts about c

    Related posts about algorithm