【模板】KMP

KMP 用在字串匹配，可以在字串 \(S\) 中找到哪些地方出現過字串 \(P\)。

核心思想是優化樸素的字串匹配過程。匹配可以視作，每個位移過後的 \(P\)，有哪些與對應的 \(S\) 子字串相等：

S  AABAABAAC
P1 AABAAc
P2  Aabaac
P3   aabaac
P4 	  AABAAC
每個都匹配到失敗為止，並且從匹配失敗之後用小寫表示

在匹配過程中，想辦法跳過會更早失敗的 \(P\)。

在匹配過程中，有時會失敗在某個地方，如在第 1 次匹配中 \(S[4] \ne P[4]\)。第 2和第 3 次匹配，會在更早的地方失敗。我們想直接跳過 2、3 次匹配。要找到下一個至少不會在 \(i<4\) 就匹配失敗的。可以發現，這相當於把 \(P\) 字串位移直到其次長前綴 = 匹配失敗前的後綴（最長就根本沒位移）：

1 2	P1 AAB[AA]c P4 [AA]BAAC

訂定函數 \(f(i)\)，代表 \(P[0,i)\) 次長共同前後綴長度（最長但不包括 \(P[0,i)\) 本身）

上面的想法，相當於以 \(i\) \(j\) 兩個指針來匹配 \(S\) 和 \(P\)，一但失敗就使 \(j\) 回到最次長前綴。定義 \(f(i)\) 可以方便地做到這件事。

轉移：\(f(i+1) = f(j)+1,\ P[j] = P[i]\)

我們來計算 \(f(i)\)。只要 \(P[f(i)] = P[i]\)，則 \(f(i+1) = f(i)+1\) 那如果不相等呢？也還有機會：

因為 \(P[0, f(i)) = P[i-f(i),i)\)，所以 \(P[0,f(f(i))) = P[i-f(f(i),i)\)。此時只要從 \(f(i)\) 退到 \(f(f(i))\)，再試試看就好了。

基底：\(f(0) = -1,\ f(1) = 0\)

顯然，\(f(1) = 0\)。那 \(f(0)\) 呢？在匹配過程中會出現 \(f(0)\)，即是當 \(S[i]\) 和 \(P[0]\) 匹配，而且還失敗的時候。這時就直接放棄這個 \(S[i]\)，從 \(S[i+1]\) 和 \(P[0]\) 開始重新匹配了。我們令 \(f(0) = -1\)，方便我們知道 \(S[i]\) 和 \(P[0]\) 匹配失敗，該直接跳過了。實作時會體現 \(-1\) 的方便性。

以下是 \(f\) 建表的實作：

f[0]=-1, f[1]=0;
for (int i=1,j; i<p.size(); i++)
{
    for (j=f[i]; j>=0 && p[j]!=p[i]; j=f[j]);
    f[i+1] = j+1;
}

以 \(i\) 遍歷 \(S\)，\(j\) 遍歷 \(P\)，對於每個 \(i\) 找到第一個與其匹配的 \(j\)

匹配 \(i\) 與 \(j\) 一但成功，就能幫下個 \(i\) 找匹配的 \(j\)。否則，就找到下一個可能與 \(i\) 匹配的 \(P\)。另外，當 \(i\) 與 \(j=0\) 匹配失敗，就 \(i++,j=0\)。

出現完全成功配對的條件，是過程中發生，\(i=|S|-1\) 和 \(j=|P|-1\) 匹配成功。下層迴圈中 \(j = |P|\)，必須使 \(j = f[j]\)。實作用到了一個細節是，p[p.size()] 會拿到 p.end()，所以不用擔心 RE。ㄦ

for (int i=0,j=0; i<s.size(); i++,j++)
{
    while (j>=0 && s[i]!=p[j]) j = f[j];
    if (j == p.size()-1) ans++;
}