POJ 2752 Seek the Name, Seek the Fame：KMP 前綴函數求邊界長度

題目大意

給定字符串 S（父親名+母親名拼接），求所有**既是前綴又是後綴**的子串長度，按遞增輸出。
多測試用例，|S| ≤ 400,000，僅小寫字母。

解法：KMP next 數組（前綴函數）

1. 構建 next[i] = 模式串 [0..i-1] 的最長真前綴同時為後綴的長度。
2. 對整個字符串 S 計算 next，則 next[|S|] 為最長邊界長度。
3. 遞歸跳轉：len = next[len] 可得到次長邊界，直到 0。
4. 收集所有邊界長度，反序輸出（或存入棧再彈出），最後補上 |S|（整串自身）。

核心代碼

#include 
using namespace std;
const int MAXN = 400005;
char s[MAXN];
int nxt[MAXN], ans[MAXN];

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

int main() {
    while (scanf("%s", s) == 1) {
        int len = strlen(s);
        getNext(s, len);
        int cnt = 0, tmp = nxt[len];
        while (tmp > 0) ans[++cnt] = tmp, tmp = nxt[tmp];
        for (int i = cnt; i >= 1; --i) printf("%d ", ans[i]);
        printf("%d\n", len);
    }
    return 0;
}

複雜度

• 時間：O(|S|) 每測試用例。
• 空間：O(|S|)。

關鍵點

• next 數組定義與標準 KMP 一致，下標從 0 開始，nxt[0] = -1 便於統一邏輯。
• 輸出順序為遞增，故反向遍歷收集的邊界長度。
• 整串自身長度 len 始終是邊界，最後補上。