如何在线性时间内求解字符串的分数周期？

要在线性时间内找到字符串的最小分数周期，核心可以借助KMP算法中的**前缀函数（Prefix Function）**实现，这是目前已知的最优O(n)解法。

核心思路 #

首先明确分数周期的定义：对于字符串s，最小的正整数p满足：对任意索引i（0 ≤ i < len(s)），都有s[i] = s[i mod p]。换句话说，s可看作某个长度为p的子串重复若干次（允许最后一次不完整）得到的结果。

前缀函数的作用是，对字符串的每个位置i，计算最长的真前缀长度，这个前缀同时也是s[0..i]的后缀。利用前缀函数的最后一个值，可快速推导出最小周期：

1. 计算字符串s的前缀函数数组prefix，这一步是严格线性时间O(n)。
2. 设字符串长度为n，令d = n - prefix[n-1]。
3. 此时d就是我们要找的最小分数周期。

验证示例 #

• 输入"cbcbcb"（n=6）：前缀函数最后一个值为4，d=6-4=2，与输出一致。
• 输入"qwertyd"（n=7）：前缀函数最后一个值为0，d=7-0=7，与输出一致。
• 输入"fghfghf"（n=7）：前缀函数最后一个值为4，d=7-4=3，与输出一致。

代码实现（Python） #

def compute_prefix_function(s):
    n = len(s)
    prefix = [0] * n
    for i in range(1, n):
        j = prefix[i-1]
        while j > 0 and s[i] != s[j]:
            j = prefix[j-1]
        if s[i] == s[j]:
            j += 1
        prefix[i] = j
    return prefix

def minimal_fractional_period(s):
    n = len(s)
    if n == 0:
        return 0
    prefix = compute_prefix_function(s)
    d = n - prefix[-1]
    return d

时间复杂度说明 #

前缀函数计算过程中，每个字符最多被访问两次（一次是i递增，一次是j回退，但j的回退总次数不会超过i的递增次数），因此整体时间复杂度为O(n)，完全符合线性时间要求。

内容的提问来源于stack exchange，提问作者KevinStewart89