查找字符串是否是迭代子字符串？

Question

我有一个字符串S.我怎么能找到字符串是否遵循S = nT.

示例:
如果
1)S ="abab"
2)S ="abcdabcd"
3)S ="abcabcabc"
4)S ="zzxzzxzzx", 则函数应返回true

但如果S ="abcb"返回false.

我想也许我们可以反复在S的子串上调用KMP然后决定.

例如:对于"abab":在"a"上拨打KMP.它返回2(两个实例).现在2*len("a")!= len(s)
在"ab"上拨打KMP.它返回2.现在2*len("ab")== len(s)所以返回true

你能建议更好的算法吗？

Answer 1

我可以想到一个启发式,如果Len(原始字符串)/ Len(子字符串)是一个正整数,则只在子字符串上调用KMP.

此外,子串的最大长度必须小于N/2.

编辑

使用这些启发式方法我写了下面的python代码,因为我的C现在生锈了

oldstr='ABCDABCD'    

for i in xrange(0,len(oldstr)/2):
       newslice=oldstr[0:i+1]
         if newslice*(len(oldstr)/len(newslice)) == oldstr:
             print 'pattern found', newslice
             break

Answer 2

您实际上只需要关心测试等于完整字符串长度除以质数的子字符串长度。原因是：如果 S 包含 T 的 n 个副本，并且 n 不是素数，则 n = ab，因此 S 实际上也包含 bT 的副本（其中“bT”表示“T 重复 b 次”）。这是anijhaw's answer的扩展。

int primes[] = { 2, 3, 5, 7, 11, 13, 17 };  /* There are one or two more... ;) */
int nPrimes = sizeof primes / sizeof primes[0];

/* Passing in the string length instead of assuming ASCIIZ strings means we
 * don't have to modify the string in-place or allocate memory for new copies
 * to handle recursion. */
int is_iterative(char *s, int len) {
    int i, j;
    for (i = 0; i < nPrimes && primes[i] < len; ++i) {
        if (len % primes[i] == 0) {
            int sublen = len / primes[i];
            /* Is it possible that s consists of repeats of length sublen? */
            for (j = sublen; j < len; j += sublen) {
                if (memcmp(s, s + j, sublen)) {
                    break;
                }
            }

            if (j == len) {
                /* All length-sublen substrings are equal.  We could stop here
                 * (meaning e.g. "abababab" will report a correct, but
                 * non-minimal repeated substring of length 4), but let's
                 * recurse to see if an even shorter repeated substring
                 * can be found. */
                return is_iterative(s, sublen);
            }
        }
    }

    return len;     /* Could not be broken into shorter, repeated substrings */
}

请注意，当递归查找更短的重复子字符串时，我们不需要再次检查整个字符串，只需检查第一个较大的重复——因为我们已经确定剩余的大重复是第一个的重复. :)