Cyclic Necklace：KMP 最小循環節與字符串最小補全

題目大意

給定字符串 s（長度 ≤ 100000），只能在左右兩端添加字符，使其成為「循環項鍊」：即字符串由某個子串重複至少兩次構成（循環節長度 < 總長度）。求最少添加字符數。

核心洞察

字符串的最小循環節長度 = n - next[n]（KMP next 數組性質）。若 n % (n - next[n]) == 0，則原串已由循環節重複構成，答案為 0。
否則需補全字符使總長度成為循環節長度的倍數，且循環次數 ≥ 2。最少添加 = (循環節長度) - (n % 循環節長度)，但若補全後總長度等於循環節長度（即循環次數=1），需再加一個循環節長度。
簡化：設 t = n - next[n]。若 n % t == 0 則 0；否則答案 = t - n % t。

KMP next 數組構建

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

完整代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1000005;
char s[MAXN];
int nxt[MAXN];

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

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

複雜度

• 時間 O(n) 每測試案例。
• 空間 O(n)。

總結

本題利用 KMP next 數組求最小循環節長度，結合補全邏輯得出最少添加字符數。關鍵公式 t = n - next[n] 是字符串周期性判定的核心結論。