M02406:字符串乘方

Kmp, http://cs101.openjudge.cn/practice/02406/

给定两个字符串a和b,我们定义ab为他们的连接。例如，如果a=”abc” 而b=”def”，则ab=”abcdef”。如果我们将连接考虑成乘法，一个非负整数的乘方将用一种通常的方式定义：a^0=””(空字符串)，a^(n+1)=a*(a^n)。

输入

每一个测试样例是一行可打印的字符作为输入，用s表示。s的长度至少为1，且不会超过一百万。最后的测试样例后面将是一个点号作为一行。

输出

对于每一个s，你应该打印最大的n，使得存在一个a，让s=a^n

样例输入

abcd
aaaa
ababab
.

样例输出

1
4
3

提示

本问题输入量很大，请用scanf代替cin，从而避免超时。

来源

Waterloo local 2002.07.01

Ac_kmp.py, 2426ms

python

'''
使用KMP算法的部分知识，当字符串的长度能被提取的"base字符串"的长度整除时，
即可判断s可以被表示为a^n的形式，此时的n就是s的长度除以"base字符串"的长度。
'''

import sys

while True:
    s = sys.stdin.readline().strip()
    if s == '.':
        break
    n = len(s)
    next = [0] * len(s)
    j = 0
    for i in range(1, n):
        while j > 0 and s[i] != s[j]:
            j = next[j - 1]
        if s[i] == s[j]:
            j += 1
        next[i] = j
    p = len(s) - next[-1]
    if n % p == 0:
        print(n // p)
    else:
        print(1)

Ac.py

python

from math import sqrt
while True:
    s = input()
    if s == '.':
        break
    judge = True
    res = 1
    for i in range(1, int(sqrt(len(s)))+1):
        n = len(s)
        if n % i != 0:
            continue
        if s == s[:i]*(n//i):
            print(n//i)
            judge = False
            break
        if s == s[:(n//i)]*i:
            res = i
    if judge:
        print(res)

Q: 两个代码都可以AC。时间复杂度分别是多少？为什么KMP反倒慢？

这是一个非常好的问题。简单来说，只循环到 $\sqrt{N}$ 是为了利用因数的对称性进行性能优化。
如果循环到 $N / 2$ ，算法也是正确的，但对于 $N = 1, 000, 000$ 这样的数据，循环次数会从 1000次 激增到 500,000次，这在 Python 中是巨大的性能差距。
以下是详细解释：
1. 数学原理：因数是成对出现的
对于任何整数 $N$ ，如果 $i$ 是 $N$ 的因子，那么 $N / i$ 一定也是 $N$ 的因子。这两个因子一定分布在 $\sqrt{N}$ 的两侧（或者相等）。
例如 $N = 36$ ， $\sqrt{36} = 6$ 。因子对如下：
$1 \times 36$
$2 \times 18$
$3 \times 12$
$4 \times 9$
$6 \times 6$ <-- 分界线
$9 \times 4$ (重复了，和 $4 \times 9$ 是一样的)
$12 \times 3$ (重复了)
...
结论： 只要遍历 $1$ 到 $\sqrt{N}$ ，就可以通过计算 $i$ 和 $N / i$ 得到所有的因子，完全不需要遍历到 $N / 2$ 。
2. 代码如何利用这一点？
代码在一次循环 i 中，实际上做了两次检查，分别对应这“一对”因子：
python
    # 假设 N = 100, i = 2 (循环还在很小的范围内)
    
    # 检查 1：把 i 当作“子串长度”
    # 对应因子对中的 (2, 50) -> 长度为 2，重复 50 次
    if s == s[:i]*(n//i): 
        print(n//i) # 找到了最大的 n，直接结束
        
    # 检查 2：把 n//i 当作“子串长度”
    # 对应因子对中的 (50, 2) -> 长度为 50，重复 2 次
    if s == s[:(n//i)]*i:
        res = i     # 记录下这个较小的 n
如果不写成 $\sqrt{N}$ ，而是写成 $N / 2$ ，那么你需要遍历到 $i = 50$ 时才能检查到“长度为50”的情况。
利用 $\sqrt{N}$ 写法，当 $i = 2$ 时，就顺便通过 n//i 把 $50$ 的情况也检查了。
3. 性能对比
题目限制 $N$ 最大可达 $1, 000, 000$ （一百万）。
如果循环到 $N / 2$ ：
Python 的 for 循环需要迭代 500,000 次。
即便很多次 continue 跳过了，光是循环本身的开销就足以让 Python 超时（Python 的循环非常慢）。
如果循环到 $\sqrt{N}$ ：
循环只需要迭代 1,000 次。
500,000 vs 1,000，这是 500倍 的差距。
总结
这就是算法竞赛中常用的数论优化。通过只枚举到平方根，同时处理 $i$ 和 $N / i$ ，可以在不遗漏任何解的情况下，将时间复杂度从线性的 $O (N)$ 降低到 $O (\sqrt{N})$ 。

M02406:字符串乘方 ​

M02406:字符串乘方