初始字符串S,长度为Len.将字符串加倍(实际上我们需要S +一半的S).从第2个位置开始,在第2个位置,从Len/2 + 1开始,搜索双字符串SS中的初始字符串S的出现.如果位置P存在这种情况,那么S是周期性的,周期为P-1.
S = abbaabbaabba Len = 12 SS = abbaabbaabbaabbaabbaabba
搜索从第2位到第7位,S在P = 5处发现,周期= 4
S = abaabaabaabb SS = abaabaabaabbabaabaabaabb
S不会出现在SS中(1和L + 1除外),不存在周期
PS Note由于有用的Venkatesh注释:我们需要添加最小可能的周期单位,偶数大小字符串的长度为L/2,奇数大小字符串的最大除数为L(如果长度为素数,则字符串不能是周期性的).简单因子分解方法具有O(N ^ 1/2)复杂度,更复杂 - O(N ^ 1/4),因此有时需要对长度进行分解以避免不必要的长字符串比较.