HDU 3746 Cyclic Necklace：KMP Next 數組的巧妙應用

問題描述

給定字符串 S，長度 n。可在尾部添加字符，使其成為某子串 T 的至少兩次重複（即 S+added = T^k, k≥2）。求最少添加字符數。

核心觀察

若 S 本身已是某子串的重複，則添加 0。否則，利用 KMP 的 next 數組：

• next[n] = 最長真前綴同時也是後綴的長度。
• 設 k = n - next[n]，則 k 為最小循環節候選長度。
• 若 n % k == 0，S 已由長度 k 的子串構成 → 答案 0。
• 否則，需補齊到下一個 k 的倍數：答案 = k - (n % k)。

推導範例

S = "aba"      n=3
next[3] = 1    ("a")
k = 3-1 = 2
n%k = 1 → 補 2-1 = 1 個字符 → "aba" + "b" = "abab" = ("ab")^2 ✓

S = "abcab"    n=5
next[5] = 2    ("ab")
k = 5-2 = 3
n%k = 2 → 補 3-2 = 1 → "abcab" + "c" = "abcabc" = ("abc")^2 ✓

完整代碼

#include 
#include 
const int MAXN = 100005;
char s[MAXN];
int nxt[MAXN];

void getNext() {
    int n = strlen(s+1);
    nxt[1] = 0;
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && s[j+1] != s[i]) j = nxt[j];
        if (s[j+1] == s[i]) j++;
        nxt[i] = j;
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%s", s+1);
        getNext();
        int n = strlen(s+1);
        if (nxt[n] == 0) { printf("%d\n", n); continue; }
        int k = n - nxt[n];
        if (n % k == 0) printf("0\n");
        else printf("%d\n", k - n % k);
    }
    return 0;
}

複雜度

KMP 求 next O(n)，每測試案例 O(n)，總線性時間，極高效。