UVA 1328 前綴周期判斷：KMP Next 數組 O(n) 解法

問題描述

給定長度 n 字符串，對每個前綴 (長度 i≥2)，判斷是否為周期串。是則輸出 i 和最大周期數 K。多測試用例，n=0 結束。

KMP Next 數組周期性質

`next[i]` = 長度 i 前綴的最長真前綴兼後綴長度。

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

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

完整代碼

#include 
#include 

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

void buildNext(const char* s, int n) {
    nxt[0] = nxt[1] = 0;
    for (int i = 1; i < n; ++i) {
        int j = nxt[i];
        while (j && s[j] != s[i]) j = nxt[j];
        nxt[i+1] = (s[i] == s[j]) ? j + 1 : 0;
    }
}

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

關鍵實現細節

1. Next 定義：代碼中 `nxt[i]` 對應長度 i 前綴，`nxt[1]=0`
2. 構建邏輯：標準 KMP 模式串自匹配，`j` 回溯
3. 周期判斷：`nxt[i] != 0` 且 `i % (i - nxt[i]) == 0`
4. 輸出格式：每測試用例後空行

複雜度

• 構建 Next：O(n)
• 檢查所有前綴：O(n)
• 總時間 O(n)，n=1,000,000 完全足夠

數學直觀理解

s = "aabaabaabaab" (n=12)
i=12, nxt[12]=9
period = 12-9=3 ("aab")
K = 12/3 = 4
驗證："aab" × 4 = "aabaabaabaab" ✓