POJ 2406 Power Strings：KMP 求字符串最大重複次數

問題描述

給定字符串 s (|s| ≤ 10⁶)，求最大 n 使 s = aⁿ（即 s 由某子串 a 重複 n 次構成）。輸入以 . 結束。

核心洞察：KMP Next 數組

設 len = |s|。KMP next[len] 表示真前綴同時為後綴的最長長度。
若 len % (len - next[len]) == 0，則最小循環節長度為 p = len - next[len]，重複次數 n = len / p。
否則 n = 1。

為什麼有效？

next[len] = 最長邊界（border）長度。字符串周期性定理：若字符串由子串重複構成，則其長度減去最長邊界長度即為最小周期。反之，若長度能被最小周期整除，則字符串確為重複結構。

KMP Next 數組構建

void getNext(const string& s, vector& next) {
    int n = s.size();
    next.assign(n+1, 0);
    next[0] = -1;
    int i = 0, j = -1;
    while (i < n) {
        if (j == -1 || s[i] == s[j]) {
            next[++i] = ++j;
        } else {
            j = next[j];
        }
    }
}

此處 next[i] 表示長度為 i 的前綴的最長邊界長度。

完整代碼

#include 
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    while (cin >> s, s != ".") {
        int n = s.size();
        vector next(n+1);
        next[0] = -1;
        for (int i = 0, j = -1; i < n; ) {
            if (j == -1 || s[i] == s[j]) next[++i] = ++j;
            else j = next[j];
        }
        int p = n - next[n];
        cout << (n % p == 0 ? n / p : 1) << '\n';
    }
    return 0;
}

複雜度

• Next 數組：O(n)
• 判斷：O(1)
• 總計：O(n)，|s|≤10⁶ 瞬時通過

暴力枚舉對比（會 TLE）

枚舉所有因子 d，檢查 s[0..d-1] 重複 n/d 次是否等於 s。最壞 O(n√n)，10⁶ 會超時。KMP 線性算法是必須的。

總結

POJ 2406 是 KMP 算法最經典應用之一：利用 next 數組求最小周期。理解「最長邊界 ↔ 最小周期」的數學關係，能秒殺字符串重複結構問題。大數據下務必用線性算法，暴力枚舉不可取。