这是一种可能的方法(由于您的周期必须相邻,因此变得更简单)。选择一个字符串。看看会不会重复。跟踪最重复的一个。
编辑实际测试过的 Python 代码:
testStrings =[ "prefixgarbagecyclecyclecyclecyclesufixgarbage",
"prefixgarbagecyclepadinggarbagecyclesufixgarbage",
"prefixgarbagecyclecyclepadinggarbageprefixgarbage",
"prefixgarbagecyclecyclecycleroundroundroundprefixgarbage",
"abcdefghijklmnopqrstuvqxyz"];
for input in testStrings:
repCountMax = 0
longestCycle = ""
repCount = 0
for i in range (1, len(input)):
for j in range( i+1, len(input)):
substring = input[i:j]
#print substring
ls = len(substring)
repCount = 1
k = j
while(substring == input[k:k+ls]):
k = k + ls
repCount = repCount +1
#print "repetition ", repCount, " of ", substring, "\n"
if (repCount > repCountMax) or ((repCount == repCountMax) and len(substring) > len(bestCycle)):
repCountMax = repCount
bestCycle = substring
if repCountMax > 1:
print "best cycle in '", input, "' is '", bestCycle,"' which is repeated ", repCountMax, " times."
else:
print "no repeated cycles found in string ", input
结果输出:
'prefixgarbagecyclecyclecyclecyclecyclesufixgarbage'中的最佳循环是'ecycl',重复4次。
“prefixgarbagecyclepadinggarbagecyclesufixgarbage”中的最佳循环是“g”,重复 2 次。
'prefixgarbagecyclecyclepadinggarbageprefixgarbage'中的最佳循环是'ecycl',重复2次。
“prefixgarbagecyclecyclecyclecycleroundroundroundprefixgarbage”中的最佳循环是“ecycl”,重复 3 次。
在字符串 abcdefghijklmnopqrstuvqxyz 中未发现重复循环
注意 - 找到的循环是ecycl
,不是cycle
。ecycl
首先发生...
第二个注意事项 - 当你不能再“击败”当前的最佳估计时,你可以通过停止来稍微提高效率 - 例如,如果你已经找到了五个重复,并且给定你正在搜索的字符串的大小,则没有' t 空间六次重复。当有大量重复时,这将提高速度。请参阅 Evgeny 的解决方案以了解实现该方法的方法。