求助：设计线性时间周期字符串判定算法并查找最短周期（当前O(nlogn)）

Hey there! Your current divide-and-conquer approach (checking if the string can split into AB=BA and recursing on half the length) makes intuitive sense, but as you noticed, it lands at an O(n log n) time complexity. Let's switch gears to a linear-time solution using the KMP algorithm's prefix function—this is the standard, efficient approach for exactly this problem.

What's the Prefix Function? #

First, a quick recap of the prefix function (often denoted as π) for a string T of length n:

• For each index i (0 ≤ i < n), π[i] is the length of the longest proper prefix of the substring T[0..i] that is also a suffix of this substring.
• The best part? We can compute this array in O(n) time with a single pass through the string.

How to Use It for Periodical Strings #

Here's the key insight that unlocks linear time:
Let d = n - π[n-1], where π[n-1] is the prefix function value for the last character of T.

• If n is divisible by d (i.e., n % d == 0), then T is a periodical string, and d is its shortest period.
• If not, T is not a periodical string.

Why This Works

Think of π[n-1] as telling us the longest chunk at the end of T that matches the start of T. The difference d = n - π[n-1] is the length of the smallest repeating unit. If the entire string length is a multiple of d, that means the string is just this unit repeated over and over.

Examples to drive this home:

• For T = "ababab" (n=6): π[5] = 4, so d = 6-4=2. 6%2=0 → shortest period is "ab".
• For T = "aaaaa" (n=5): π[4] =4, d=1. 5%1=0 → shortest period is "a".
• For T = "abcabcab" (n=8): π[7]=5, d=3. 8%3≠0 → not a periodical string.

Step-by-Step Algorithm #

1. Compute the prefix function array:

   function computePrefixFunction(T):
       n = length(T)
       π = array of 0s with length n
       for i from 1 to n-1:
           j = π[i-1]
           while j > 0 and T[i] != T[j]:
               j = π[j-1]
           if T[i] == T[j]:
               j += 1
           π[i] = j
       return π
   

2. Check periodicity and find the shortest period:
   • Calculate π using the function above
   • Let n = length(T)
   • Compute d = n - π[n-1]
   • If n % d == 0:
     • T is periodical, with shortest period length d (or the substring T[0..d-1])
   • Else:
     • T is not periodical

Time Complexity #

The prefix function computation runs in O(n) time (each step either increments j or reduces it, but j can't exceed n total increments). The subsequent check is O(1), so the entire algorithm is linear time O(n)—exactly what you're aiming for!

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