c - 查找字符串是否是 C 中的迭代子字符串算法？

Question

问题描述

我有一个字符串 S。我如何找到该字符串是否遵循 S = nT ？

例子:

函数应该返回真如果

1) S = "abab"  
2) S = "abcdabcd"  
3) S = "abcabcabc"  
4) S = "zzxzzxzzx"  

但是如果 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(original string)/Len of(sub string) 是正整数，则仅在子字符串上调用 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