KMP 算法 next 數組深度解析：前綴後綴匹配與最短週期應用

next 數組是 KMP 核心，next[i] 表示模式串前 i 個字符（0-indexed 通常指前 i 個字符的最長真前綴同時也是後綴的長度）。

標準構建代碼

void getNext(const string& pat, vector& next) {
    int m = pat.size();
    next.assign(m+1, 0);
    next[0] = -1;
    int j = -1;
    for (int i = 0; i < m; ) {
        if (j == -1 || pat[i] == pat[j]) {
            next[++i] = ++j;
        } else {
            j = next[j];
        }
    }
}

幾何意義

失配時，模式串向右移動 j - next[j] 位，保證已匹配的前綴與新對齊的後綴一致。next[j] 即為「前 j 個字符的最長邊界長度」。

兩大應用

1. 求字符串最短週期

長度為 L 的字符串，若 L % (L - next[L]) == 0，則最短週期為 L - next[L]。例如 "ababab"，next[6]=4，週期=2 ("ab")。

2. 統計前綴出現次數

利用 next 樹統計每個前綴在串中出現次數（HDU 3746 Cyclic Necklace）。

推薦練習題

• HDU 1358 Period（最短週期）
• HDU 3746 Cyclic Necklace（前綴計數）

理解 next 數組的「邊界」本質，是掌握 KMP 及其變體的關鍵。