POJ 1961 解題報告：KMP 算法求字串周期性

問題描述

給定字串，找出所有前綴中重複出現超過一次的長度及重複次數。例如 ababab：前 4 字元重複 2 次，前 6 字元重複 3 次。

KMP Next 陣列核心洞見

next[i] 表示前 i 字元的最長真前綴同時也是後綴的長度。對於長度 L 的前綴，若 L % (L - next[L]) == 0，則該前綴由長度 L - next[L] 的子串重複構成，重複次數為 L / (L - next[L])。

程式碼關鍵點

void Get_next() {
    int j = 1, k = 0;
    next[1] = 0;
    while (j <= n + 1) {          // 多算一位 next[n+1] 便於統一處理
        if (k == 0 || s[j] == s[k]) { ++j; ++k; next[j] = k; }
        else k = next[k];
    }
}

int main() {
    // ... 讀入資料 ...
    Get_next();
    for (int i = 2; i <= n; ++i) {
        int period = i + 1 - next[i + 1];  // 週期長度
        if (i % period == 0) {
            int cnt = i / period;
            if (cnt != 1) printf("%d %d\n", i, cnt);
        }
    }
}

以 ababab 為例

• i=4：period = 5 - next[5] = 2，4 % 2 == 0 → 重複 2 次
• i=6：period = 7 - next[7] = 2，6 % 2 == 0 → 重複 3 次

複雜度與技巧

• 時間 O(N)，空間 O(N)，極度高效。
• 陣列下標從 1 起始，字串尾附加 # 哨兵，簡化邊界判斷。
• 輸入以 n=0 結束，支援多測資。

延伸應用

此模式廣泛應用於：DNA 序列分析、文本壓縮、病毒特徵碼檢測等需快速識別重複模式的場景。