算法分析
两个结论背一下:
1. KMP算法得到的ne数组,n - ne[n]
是长度为n的字符串的最小循环节
2. 所有循环节的长度都是最小循环节长度的整数倍
3. 注意这里的循环节并不能完整覆盖整个字符串的,最后几位可能只有循环节的前几个字母
根据上面两个定理可知:
只要n - ne[n]
能被n
整除,说明这个循环节在长度为n
的字符串内是完整的,不存在循环节不能完整覆盖最后几个字母的情况,其次本题中需要循环节出现的次数大于等于$1$,所以要保证(n // n - ne[i]) > 1
时间复杂度 $O(n)$
python 代码
N = 1000010
ne = [0] * N
T = 1
while True:
n = int(input())
if n == 0: break
w = ' ' + input()
j = 0
for i in range(2, n + 1):
while j > 0 and w[i] != w[j + 1]:
j = ne[j]
if w[i] == w[j + 1]:
j += 1
ne[i] = j
print("Test case #%d" % T)
T += 1
for i in range(1, n + 1):
t = i - ne[i]
if i % t == 0 and i // t > 1:
print(i, i//t, end = " ")
print()
print()