• KMP

  KMP算法全称Knuth-Morris-Pratt算法，可以在\(O(n + m)\)的时间复杂度下进行在长度为\(n\)的字符串中查找另一个长度为\(m\)的字符串出现的所有位置，同时也能在\(O(n)\)的时间复杂度下查找一个长度为\(n\)的字符串中，前缀和后缀相同的最大长度。
  首先思考一下，如何暴力地在一个字符串中查找另一字符串出现的所有位置，很快可以找到这样一种思路：枚举字符串\(s1\)中所有字符\(s1[i]\)作为要查找的字符串\(s2\)的首个字符，然后向后遍历判断这个字符之后是否存在\(s2\)，实现代码如下：

#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	string a, b;
	int ans = 0;
	cin >> a >> b;
	int la = a.length(), lb = b.length();
	for (int i = 0; i < la; ++i) {
		if (a[i] == b[0]) {
			for (int j = 0; j < lb; ++j) {
				if (a[i + j] != b[j])  break;
				if (j == lb - 1) ++ans;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

显然，此时程序的复杂度是\(O(nm)\)的，有位大佬曾言：

“算法时间复杂度的优化本质上就是减少无用的操作”

我们可以发现，在上一个代码中，当我们枚举一个字符\(s[i]\)时，这个字符很可能在我们枚举\(s[i-1]\)的时候就被枚举过了，所以我们要对这一部分操作进行精简。
我们引入一个数组\(nxt[i]\)，表示在字符串\(s1[0\sim i]\)中，前缀和后缀相等的最大长度。
所以当我们模式串匹配文本串出现失配时，我们要跳到这个位置对应的\(nxt\)，也就是后面匹配不上时，就回到前面与已匹配