HDU 3746 Cyclic Necklace：KMP 失敗函數求最小循環節擴展

問題建模

給定字符串，求需在尾部添加最少字符，使其成為由 n (n≥2) 個相同循環節組成的字符串。實質是求字符串的最小循環節長度，並計算補齊至整數倍所需字符數。

核心原理：LCPS (Longest Common Prefix Suffix) 數組

利用 KMP 的 next 數組（即 LCPS），可在 O(n) 時間求出最長真前綴兼真後綴長度。設字符串長度為 len，最小循環節長度 cir = len - next[len]。

分類討論

• cir == 1：全同字符，無需添加，輸出 0。
• len == cir：無真前綴後綴匹配，需添加 cir 個字符構成兩個循環節。
• len % cir == 0：已為整數倍循環節，輸出 0。
• 其餘情況：需添加 cir - (len % cir) 個字符補齊下一個循環節。

代碼實現要點

void GetLCPS() {
    int j = 0, k = -1;
    int len = strlen(a);
    next[0] = -1;
    while (j < len) {
        if (k == -1 || a[k] == a[j]) {
            next[++j] = ++k;
        } else {
            k = next[k];
        }
    }
}

主函數中根據上述四種情況直接輸出答案，邏輯清晰高效。

總結

本題是 KMP 失敗函數在循環字符串問題中的經典應用，通過 next 數組快速獲取最小循環節，再以模運算決定補齊長度，體現了字符串周期性分析的核心思想。