KMP(Knuth–Morris–Prat) 算法是一种能够在 $O(N+M)$ 时间内完成字符串匹配的算法，其中 $N$ 是匹配串的长度，$M$ 是模式串的长度。当模式串与匹配串进行匹配，且最新一个字符匹配失败时，朴素算法会丢弃掉所有已经匹配的字符并从头开始，而KMP算法利用 前缀函数 ，充分利用了已经匹配的子串的信息。

KMP算法

首先介绍前缀函数。前缀函数 $\pi (n)$ 是这样一个函数：对于串 $S$ ，我们记它的前缀 $S[1,2,...,n]$ 为 $Perfix(S,n)$ ，后缀为 $Suffix(S,n)$ ，$\pi (n)$ 就等于使得 $Suffix(Perfix(S,n),k)=Perfix(S,n)$ 成立的最大的 $k$ 。简单来说，我们取 $S$ 的前缀 $S^n$ ，$\pi (n)$ 就是 $S^n$ 最大的前缀与后缀相匹配的长度。

有了前缀函数，当模式串 $P$ 在串 $S$ 中进行匹配，且在 $P$ 的第 $j$ 项与 $S$ 的第 $i$ 项匹配失败（$P_j\ne S_i$ ）时，我们就不需要从头开始匹配，因为我们已经知道了 $P[1,...,j]=S[i-j+1,...,i]$ ，利用前缀函数可以得到 $P[1,...,\pi (j)]=S[i-\pi (j)+1,...,i]$ ，因此直接从 $\pi (j)$ 项开始匹配就行了。

下面是一个示例代码：

std::vector<int> ans;
std::string p,s;

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

其中， $next[x]$ 就是前缀数组，当程序运行结束后， $ans$ 数组中就存储了 $P$ 在 $S$ 中每一次出现的起始位置。

前缀函数的求法

不难发现，求前缀函数的过程其实类似 $P$ 与自身相匹配的过程。我们可以参照 $P$ 与 $S$ 匹配的思路，对于 $\pi (n)$ ，它的前面是 $\pi (n-1)$ ，如果此时 $P_n=P_{\pi (n-1)+1}$ ，说明 $\pi (n)=\pi (n-1)+1$ ；否则就沿着 $\pi (n-1)$ 往前跳，直到找到匹配的：

int next[N];

next[0]=-1;
for(int i=1,j=-1;i<p.length();i++)
	while(j >= 0 && p[j+1] != p[i])
		j=ne[j];
	if(p[j+1]==p[i])
		j++;
	ne[i] = j;
}

时间复杂度分析

看上去，KMP算法使用了二重循环，这是否意味着它的时间复杂度是平方级的呢？并不是。
从上面的代码可以看出，在每一次循环时，$j$ 最多增大 $1$ ，而每次 $j=ne[j]$ 都至少使得 $j$ 减少 $1$ 。而 $j$ 始终是一个非负数，因此 for 中的 while 循环执行的总次数不会超过 j++ 执行的次数。而 j++ 在求前缀函数中最多执行 $M$ 次，在匹配时最多执行 $N$ 次，故 while 的次数也不超过这一值。因此，总的时间复杂度为 $O(2N+2M)=O(N+M)$ 。