T01961: 前缀中的周期

KMP, http://cs101.openjudge.cn/practice/01961/

一个字符串的前缀是从第一个字符开始的连续若干个字符，例如"abaab"共有5个前缀，分别是a, ab, aba, abaa, abaab。

我们希望知道一个N位字符串S的前缀是否具有循环节。换言之，对于每一个从头开始的长度为 i （i 大于1）的前缀，是否由重复出现的子串A组成，即 AAA...A （A重复出现K次,K 大于 1）。如果存在，请找出最短的循环节对应的K值（也就是这个前缀串的所有可能重复节中，最大的K值）。

输入

输入包括多组测试数据。每组测试数据包括两行。第一行包括字符串S的长度N（2 <= N <= 1 000 000）。第二行包括字符串S。输入数据以只包括一个0的行作为结尾。

输出

对于每组测试数据，第一行输出 "Test case #“ 和测试数据的编号。接下来的每一行，输出前缀长度i和重复测数K，中间用一个空格隔开。前缀长度需要升序排列。在每组测试数据的最后输出一个空行。

样例输入

3
aaa
12
aabaabaabaab
0

样例输出

Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4

题意：给定一个长度为N的字符串S，对S的每一个前缀S[1~i]，如果它的最大循环次数大于1，则输出该前缀的长度和最大循环次数。

python

'''
这是一个字符串匹配问题，通常使用KMP算法（Knuth-Morris-Pratt算法）来解决。
使用了 Knuth-Morris-Pratt 算法来寻找字符串的所有前缀，并检查它们是否由重复的子串组成，
如果是的话，就打印出前缀的长度和最大重复次数。
'''

# 得到字符串s的前缀值列表
def kmp_next(s):
  	# kmp算法计算最长相等前后缀
    next = [0] * len(s)
    j = 0
    for i in range(1, len(s)):
        while s[i] != s[j] and j > 0:
            j = next[j - 1]
        if s[i] == s[j]:
            j += 1
        next[i] = j
    return next


def main():
    case = 0
    while True:
        n = int(input().strip())
        if n == 0:
            break
        s = input().strip()
        case += 1
        print("Test case #{}".format(case))
        next = kmp_next(s)
        for i in range(2, len(s) + 1):
            k = i - next[i - 1]		# 可能的重复子串的长度
            if (i % k == 0) and i // k > 1:
                print(i, i // k)
        print()


if __name__ == "__main__":
    main()

python

# 23n2300017735(夏天明BrightSummer)
case = 0
while n := int(input()):
    case += 1
    print(f"Test case #{case}")
    s = input()
    ans = {}
    for i in range(1, n):
        k = 1
        while (k+1)*i <= n and s[:i] == s[k*i:(k+1)*i]:
            k += 1
            if i*k not in ans:
                ans[i*k] = k
    for r in ans.items():
        print(*r)
    print()

T01961: 前缀中的周期 ​

T01961: 前缀中的周期