KMP算法_牛客博客

KMP算法的作用：给你一个长为n的字符串s和一个长为m的字符串p，求s中等于p的连续子串的出现位置或者出现次数

原理：当我们进行字符串匹配失配之后我们回溯到k，k满足从当前i位置的一个后缀等于适配字符串的一个k前缀，我们预先用nxt数组处理并且存储k的值，我们用p存储的是在当前位置能够适配字符串p的第几位，当p[i]==m的时候也就是一次适配成功

复杂度：O(n + m)

板子：

int n, m;
int nxt[N], f[N];
string s, p;

void kmp(){
	int j = 0;
	nxt[1] = 0;
	for(int i = 2; i <= n; i ++){
		while(j > 0 && p[j + 1] != p[i]){
			j = nxt[j];
		}
		if(p[j + 1] == p[i]) j ++;
		nxt[i] = j;
	}	
	
	j = 0;
	for(int i = 1; i <= m; i ++){
		while((j == n) || (j > 0 && p[j + 1] != s[i])){
			j = nxt[j];
		}
		if(p[j + 1] == s[i]) j ++;
		f[i] = j;
	}
}

void solve(){
	cin >> n >> p >> m >> s;
	p = ' ' + p;
	s = ' ' + s;
	kmp();
	int res = 0; 
	//输出位置，这里是从0开始计数，从1开始把i-n+1即可 
	for(int i = 1; i <= m; i ++){
		if(f[i] == n){
			cout << i - n << ' ';
            res ++;
		}
	}
	//输出数量
	cout << res << '\n'; 
}

例1:P3375 【模板】KMP 字符串匹配

#include<bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
//#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1000010, mod = 998244353;
const int Mod = 1e9 + 7, INF = 0x3f3f3f3f;

int n, m;
int nxt[N], f[N];
string s, p;

void kmp(){
	nxt[1] = 0;
	int j = 0;
	for(int i = 2; i <= m; i ++){
		while(j > 0 && p[j + 1] != p[i]) j = nxt[j];
		if(p[j + 1] == p[i]) j ++;
		nxt[i] = j;
	}
	
	j = 0;
	for(int i = 1; i <= n; i ++){
		while(j == m || (j > 0 && s[i] != p[j + 1])) j = nxt[j];
		if(s[i] == p[j + 1]) j ++;
		f[i] = j;
	}
}

void solve(){
	cin >> s >> p;
	n = s.size(), m = p.size();
	s = ' ' + s;
	p = ' ' + p;
	
	kmp();
	
	for(int i = 1; i <= n; i ++){
		if(f[i] == m){
			cout << i - m + 1 << '\n';
		}
	}
	
	for(int i = 1; i <= m; i ++){
		cout << nxt[i] << ' ';
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t --){
		solve();
	}
	return 0;
}

例2：Secret Word

思路：既然题意让我们寻找s的子串，使得它的翻转是s的一个前缀，那我们先把s整体翻转得到p，把这个翻转得到的p作为文本字符串，用s作为匹配字符串取匹配它即可

#include<bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
//#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N = 100010, mod = 998244353;
const int Mod = 1e9 + 7, INF = 0x3f3f3f3f;

string s, p;
int n;
int nxt[N],f[N];

void kmp(){
	int j = 0;
	nxt[1] = 0;
	for(int i = 2; i <= n; i ++){
		while(j > 0 && p[i] != p[j + 1]) j = nxt[j];
		if(s[i] == p[j + 1]) j ++;
		nxt[i] = j; 
	}
	
	j = 0;
	for(int i = 1; i <= n; i ++){
		while(j > 0 && s[i] != p[j + 1]) j = nxt[j];
		if(s[i] == p[j + 1]) j ++;
		f[i] = j;
	}
}
void solve(){
	cin >> p;
	n = p.size();

	s = p;

	reverse(s.begin(), s.end());
	s = ' ' + s;
	p = ' ' + p;
	kmp();
	
	int ma = -1;
	
	for(int i = 1; i <= n; i ++){
		if(f[i] > ma){
			ma = f[i];
		}
	}
	for(int i = ma; i >= 1; i --) cout << p[i];
	cout << '\n';
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while(t --){
		solve();
	}
	return 0;
}

例3：MUH and Cube Walls

思路：预先处理差分，然后套kmp板子即可

#include<bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
//#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N = 200010, mod = 998244353;
const int Mod = 1e9 + 7, INF = 0x3f3f3f3f;

void solve(){
	ll n, m;
	cin >> n >> m;
	vector<ll> a(n + 1), b(m + 1), f(n + 1),nxt(m + 1);
	
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1; i <= m; i ++) cin >> b[i];
	
	for(int i = 1; i < n; i ++) a[i] -= a[i + 1];
	for(int i = 1; i < m; i ++) b[i] -= b[i + 1];
	
	if(m == 1){
		cout << n << '\n';
		return;
	}
	
	n --, m --;
	int j = 0;
	for(int i = 2; i <= m; i ++){
		while(j > 0 && b[i] != b[j + 1]) j = nxt[j];
		if(b[j + 1] == b[i]) j ++;
		nxt[i] = j;
	}
	
	j = 0;
	
	for(int i = 1; i <= n; i ++){
		while(j == m || (j > 0 && a[i] != b[j + 1])) j = nxt[j];
		if(a[i] == b[j + 1]) j ++;
		f[i] = j;
	}
	int ans = 0;
	for(int i = 1; i <= n; i ++){
		if(f[i] == m) ans ++;
	}
	
	cout << ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t --){
		solve();
	}
	return 0;
}