HDU 3746 Cyclic Necklace：KMP 求最小循環節補齊

題目大意

• 字符串 `S`（長度 `L ≤ 1e5`），只能在**左右兩端**添加字符。
• 目標：使結果字符串由 ≥2 個相同子串拼接而成（即存在長度 `t` 的循環節，`L' % t == 0` 且循環節數 ≥ 2）。
• 求最少添加字符數。

KMP Next 數組與最小循環節

• 構建 `next` 數組（`next[i]` = 模式串前 `i` 字符的最長真前綴後綴長度）。
• 最小循環節長度 `t = L - next[L]`。
• 若 `L % t == 0` 且 `L/t ≥ 2`：已滿足，添加 0。
• 否則：需補齊至 `t` 的倍數，添加 `t - (L % t)` 字符。

完整代碼

#include 
using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        string s; cin >> s;
        int L = s.size();
        vector nxt;
        getNext(s, nxt);
        int t = L - nxt[L];
        if (L % t == 0 && L / t >= 2) cout << 0 << "\n";
        else cout << t - (L % t) << "\n";
    }
    return 0;
}

範例

S = "abca" (L=4)
next = [-1,0,0,0,1] -> t = 4-1=3
L%t = 1 -> add 3-1=2 -> "abca" + "bc" = "abcabc" (t=3, 2 cycles) ✓

複雜度

• KMP 構建 `next`：O(L)。
• 每測試用例 O(L)，總長 ≤ 1e7 可接受。