POJ 2752 解題報告：KMP 尋找字串所有邊界

問題描述

給定字串，輸出所有既是真前綴又是真後綴的子串長度（即字串的所有邊界），按遞增序列印。例如 ababa 的邊界長度為 1, 3。

演算法邏輯

利用 KMP next 陣列性質：next[i] 指向長度 i 前綴的最長邊界。從 next[n+1] 開始，沿 next[] 鏈條回溯，即可枚舉所有邊界長度。

關鍵程式碼

void Get_next() {
    int j = 1, k = 0;
    next[1] = 0;
    while (j <= n + 1) {
        if (k == 0 || s[j] == s[k]) { ++j; ++k; next[j] = k; }
        else k = next[k];
    }
}

int main() {
    while (scanf("%s", t) != EOF) {
        n = strlen(t);
        for (int i = 1; i <= n; ++i) s[i] = t[i-1];
        s[++n] = '#';  // 哨兵
        Get_next();
        int k = 0;
        result[k++] = n;  // 字串全長也是邊界（自身）
        for (int i = n; i != 1; i = next[i])
            if (next[i] != 1) result[k++] = next[i];
        for (int i = k - 1; i > 0; --i) printf("%d ", result[i] - 1);
        printf("%d\n", result[0] - 1);
    }
}

執行流程圖解

以 ababa (n=5) 為例：

1. 建立 next：[0,1,1,2,3,4,?]
2. 從 i=6 回溯：next[6]=4 → next[4]=2 → next[2]=1
3. 收集 {6,4,2}，減 1 後輸出 1 3 5（含自身長度）

技術細節

• 陣列大小 400008 支援長字串。
• 哨兵 # 確保 next[n+1] 正確計算。
• 輸出邏輯先存陣列再反向列印，保證遞增序。

應用場景

字串邊界枚舉是字串演算法基礎工具，用於：字串壓縮（LZ77 變體）、生物資訊學重複序列偵測、字串最小表示法求解等。