写在前面

KMP算法

典型例题

输入
第一行一个整数N，表示测试数据组数。
接下来的N*2行，每两行表示一个测试数据。在每一个测试数据中，第一行为模式串，由不超过10^4 个大写字母组成，第二行为原串，由不超过10^6 个大写字母组成。
其中N<=20
输出
对于每一个测试数据，按照它们在输入中出现的顺序输出一行Ans，表示模式串在原串中出现的次数。

解法

暴力解：遍历原串每一个元素逐一匹配模式串，这样带来的复杂度是o(n*m)，n为原串长度，m为模式串长度，如果原串和模式串都很大的情况下这样的复杂度是很难接受的。

逐一匹配的想法是简单的，问题就在于这样的暴力匹配，完全没有用到前面匹配过程当中的任何信息。分析这O(n*m)的复杂度来自哪里就可以有一个清晰的认识了。
kmp算法的核心就在于匹配过程当中模式串的回溯过程。暴力解当中对于模式串一旦不匹配就会回溯到模式串的头部和下一个原串的元素进行匹配，对于原串来说上一次匹比较过的位置这一次还可能会被比较。对于kmp算法而言，妙就妙在模式串的回溯不会一下子回溯到头而是回溯到前面的某一个位置，同时原串根本不会回溯，也就是说原串的遍历是一直向前的，如果某个位置发生了失配，模式串进行回溯直到模式串回溯到头还没匹配上，此时原串才往后遍历下一个位置。对于原串的任意一个位置只被考虑和模式串进行一次匹配，而暴力解当中原串的任意一个位置的元素可能会被拿出来和模式串匹配m次。

kmp算法的步骤分为2步：

  • 根据模式串构造next数组
  • 使用next数组对原串进行匹配

构建next数组

对于next数组的构建从理论上说：
next[i] 等于模式串当中除去第i位之前的子串当中前缀与后缀串当中匹配上的最大的子串的长度。这么一说有点抽象，举个例子来说吧：比如模式串为abcabdo
那么对应的d位置的next[5] = 2，同理next[4] = 1,next[3] = 0,next[2] = 0,next[1] = 0;
但是对于next[0] 我们需要将其设置为-1。这是为了防止在第一个位置发生失配时一直循环。
从代码实现上来说：
虽然从理论上我们去逐个分析next数组的值是很简单的但是代码实现上却有难度。但是也是可以发现，我们可以利用前面位置求出的next数组的值作为这次的判断基础，不需要再从头判断，也就是说求出next数组的过程是一个动态规划填表的过程。next[i]表示的是当i位置出现失配的时候应该回溯到next[i]位置去进行再次匹配，那么对于next[i]而言如果str_m[i-1]==str_m[next[i-1]] 也就是说对于i位置而言前缀和后缀匹配的最大长度比i-1位置多1，此时next[i] = next[i-1] + 1。否则递归的往前去找next[next[i-1]]继续匹配直到出现next为-1的情况为止。

kmp代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> make_next(string& str_m) {
	int n = str_m.size();
	if(n==1) return vector<int> {-1};
	vector<int> next(n,0);
	next[0] = -1;
	next[1] = 0;
	int j = 0;
	for(int i=2;i<n;++i) {
		j = next[i-1];
		while(j!=-1&&str_m[i-1]!=str_m[j])//从后往前找到第一个匹配上i-1位置的模式串的位置
			j = next[j];
		next[i] = j + 1;//如果为-1则该值为0 如果不是则说明匹配上了 新的最大长度为前者加一
	}
	return next;
}

int kmp_algorithm(string& str_m,string& str_p) {
	int m = str_m.size(),n = str_p.size();
	if(m>n||m==0||n==0) return 0;
	if(m==n) return str_m==str_p;

	int count = 0;
	vector<int> next = make_next(str_m);
	int j = 0;
	for(int i=0;i<n;) {
		if(j!=-1) {
			if(str_m[j]==str_p[i]) {
				if(j==m-1) {//找到一个匹配项
					++count;
					j = next[j];//此时模式串回溯即可
				}
				else {
					++i;
					++j;
				}
			}//如果发生失配 模式串回溯
			else {
				j = next[j];
			}
		}
		else {//如果模式串已经失配到开头说明原串此位置无法匹配应该往后
			++i;
			j = 0;//模式串复位
		}
	}
	return count;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

	int N;
	cin >> N;
	vector<int> res;
	for(int i=0;i<N;++i) {
		string str_m,str_p;
		cin >> str_m >> str_p;
		res.push_back(kmp_algorithm(str_m,str_p));
	}
	for(auto each : res)
		cout << each << endl;
	return 0;
}