字符串匹配是一个很常见的问题，例如从一个长的字符串：saippuakauppias，我们要匹配模式字符串pp。可以用暴力破解法，复杂度是$O(nm)$n是长字符串的长度，m是模式字符串的长度。

于是几个聪明的人发明了KMP算法。

暴力破解法的一个很大的问题就是需要一个一个比对，如果比对错了，那么下次就从下一个还是一个一个比对。这样的坏处就是没有好好利用之前已经得到的信息。KMP算法就很好的解决了这个问题，可以利用之前的信息。

$\pi$（pi）表

KMP算法最重要的一个就是$\pi$表。

什么是$\pi$表？一句话概括：预处理模式串P中最长相同前缀和后缀的长度。

举一个例子就清晰了。比如abab，这个字符串最长相同前缀和后缀就是ab，也就是2。

为什么是可以的？给一个比较直观的例子。

T: abababc
P: ababc

以0作为开头索引，pi[3]就指的是P的前四个，即abab，因此pi[3]=2。

此时我们开始匹配，可以看到前面四个都是匹配上的，但是字符c没有匹配上，如果使用暴力破解法，我们就需要移动下一位重新进行匹配。参考下面：

T: abababc
P:  ababc

然而由于我们提前处理了一个pi（$\pi$）表，可以知道在c之前最长前缀后缀是2，那么直接把前缀移动到后缀这个位置上不就匹配上了吗？参考：

T: abababc
P:   ababc

这样就利用了之前得到 的信息加速了算法。类似于dp 的思想。

知道了pi表后，如何得到pi表？参考一下c++代码：

vector<int> pi(string P) {
	auto N = P.size();
	vector<int> pi_s(N);
	// j表示最大前缀后缀长度
	for(int i=1, j=0; i < N; i++) {
		// 如果没有匹配上，那么j就往前面看，看看是否有更短的前缀后缀长
		while(j>0 && P[j] != P[i]) {
			j = pi_s[j-1];
		}
		// 如果相等，j对应+1
		if(P[j]==P[i]) {
			j++;
		}
		pi_s[i] = j;
	}
	return pi_s;
}

有了pi表之后，查找子串就简单了，参考如下c++代码：

int kmp_search(string P, string S) {
	// 查找
	auto pi_s = pi(P);
	int j = 0;
	for(int i=0; i<n; ++i) {
		while(j>0 && P[j] != S[i]) {
			// 核心：如果没有匹配上，j就是上一个前缀的长度
			// 理由：由于当前j前面的后缀和前缀是一样的，那么这一段我们就可以直接不用比了
			j = pi_s[j-1];
		}
		if(T[i] == P[i]) {
			j++;
		}
		if(j==m) {
			return i - m + 1;
		}
	}
	return -1;
}