HDU 1358 Period：KMP Next 數組求字符串周期的經典應用

問題描述

給定長度 N (≤ 1,000,000) 的字符串 S，對每個前綴 S[0..i-1] (i ≥ 2)，判斷其是否為周期串。若是，輸出長度 i 和最大周期數 K (K > 1)。周期串定義：存在子串 A，使得前綴 = A^K (A 重複 K 次)。

KMP Next 數組核心性質

next[i] 表示前綴 S[0..i-1] 的最長真前綴同時也是後綴的長度。關鍵結論：

前綴長度 i 是周期串 ⟺ next[i] > 0 且 i % (i - next[i]) == 0

此時最小周期長度 = i - next[i]，最大周期數 K = i / (i - next[i])。

直觀理解

S = "aabaabaabaab" (長度 12)
i=12, next[12]=9
最小周期 = 12-9=3 ("aab")
K = 12/3 = 4
驗證："aab" 重複 4 次 = "aabaabaabaab" ✓

完整 AC 代碼

#include <cstdio>
#include <cstring>

const int MAXN = 1000005;
char s[MAXN];
int nxt[MAXN];

void getNext(const char* s, int len) {
    nxt[0] = -1;
    int i = 0, j = -1;
    while (i < len) {
        if (j == -1 || s[i] == s[j]) {
            ++i; ++j;
            nxt[i] = j;
        } else {
            j = nxt[j];
        }
    }
}

int main() {
    int n, caseNo = 0;
    while (scanf("%d", &n) == 1 && n) {
        scanf("%s", s);
        getNext(s, n);
        printf("Test case #%d\n", ++caseNo);
        for (int i = 2; i <= n; ++i) {
            int period = i - nxt[i];
            if (nxt[i] > 0 && i % period == 0) {
                printf("%d %d\n", i, i / period);
            }
        }
        printf("\n");
    }
    return 0;
}

關鍵實現細節

1. Next 數組定義：代碼中 nxt[i] 存儲長度為 i 的前綴的最長公共前後綴長度（nxt[1]=0）
2. 數組大小：N ≤ 1,000,000，必須開 MAXN = 1000005 以上
3. 輸入處理：多測試用例，以 0 結束
4. 輸出格式：每個測試用例後空行

複雜度分析

• 構建 Next：O(N)
• 遍歷檢查：O(N)
• 總時間 O(N)，空間 O(N)，完美通過百萬級數據

延伸應用

同樣的 Next 數組性質還可用於：

• 字符串最小循環節
• 字符串匹配 (KMP 算法核心)
• 最小表示法輔助判斷