# 【模板】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$ 字串位移直到其次長前綴 = 匹配失敗前的後綴（最長就根本沒位移）：

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]$

只要 $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++;
}