02406: 字符串乘方

strings, 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

364ms.

python

while True:
    s = input().strip()
    if s == '.':
        break
    len_s = len(s)
    max_power = 1
    for i in range(1, len_s // 2 + 1):
        if len_s % i == 0:
            a = s[:i]
            if a * (len_s // i) == s:
                max_power = max(max_power, len_s // i)
    print(max_power)

内置函数更快，94ms.

python

import sys


def find_max_power(s):
    n = len(s)
    for i in range(1, n // 2 + 1):
        if n % i == 0:
            a = s[:i]
            #if s == a * (len_s // i):  # 判断是否能重复构成原字符串
            #if s.count(a) * len(a) == n:
            if s.startswith(a * (n // i)):
                return n // i
    return 1  # 如果没有找到合适的周期，返回 1


def main():
    input = sys.stdin.read
    data = input().splitlines()

    for s in data:
        s = s.strip()
        if s == '.':
            break
        print(find_max_power(s))


if __name__ == "__main__":
    main()

KMP 1570ms

你需要找到最大的 ( n ) 使得字符串 ( s ) 可以被分解成 ( a^n )，即 ( s ) 由某个子串 ( a ) 重复 ( n ) 次构成。

解题思路

枚举可能的周期长度：
- 设字符串长度为 len_s，枚举 i 作为可能的周期（i 必须是 len_s 的因子）。
检查周期是否有效：
- 取 a = s[:i]，然后验证 s == a * (len_s // i)。
优化：
- 如果找到了最长的 i 满足上述条件，直接返回 len_s // i 作为 n。

优化实现

采用 KMP 的前缀函数（pi 数组） 来高效求解 a 的长度：
- pi[len_s] 给出字符串 s 的最长相同前后缀长度 l。
- 最小周期 p = len_s - l（如果 len_s % p == 0，则 s 是 a^n）。
- 最终 n = len_s / p。

python

import sys

def compute_prefix_function(s):
    """ 计算 KMP 前缀函数（pi 数组）"""
    n = len(s)
    pi = [0] * n
    j = 0  # 当前匹配的最长前后缀
    for i in range(1, n):
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

def find_max_n(s):
    """ 计算最大的 n，使得存在 a 使得 s = a^n """
    len_s = len(s)
    pi = compute_prefix_function(s)
    p = len_s - pi[-1]  # 最小周期长度
    if len_s % p == 0:
        return len_s // p
    return 1

def main():
    input = sys.stdin.read
    data = input().splitlines()
    
    for s in data:
        s = s.strip()
        if s == '.':
            break
        print(find_max_n(s))

if __name__ == "__main__":
    main()

优化点

O(n) 复杂度求解：
- 直接用 KMP 前缀函数 计算最小周期，避免 O(n^2) 复杂度的字符串拼接和重复计算。
高效 I/O 处理：
- 使用 sys.stdin.read() 处理大规模输入，避免 input() 带来的性能损失。

这种方法的 时间复杂度为 O(n)，可以轻松处理长度为百万的字符串。

02406: 字符串乘方 ​

02406: 字符串乘方