字符串匹配

参考资料

• 字符串匹配 - OI Wiki
• 前缀函数与 KMP 算法 - OI Wiki
• KMP算法 - 维基百科
• 拉宾-卡普算法 - 维基百科

KMP 算法

int kmp(string s,string t)
{
	int n=s.size(),m=t.size();
	for(int i=1;i<m;i++)
	{
		int j=nxt[i-1];
		while(j&&t[i]!=t[j])j=nxt[j-1];
		if(t[i]==t[j])j++;
		nxt[i]=j;
	}
	int j=0;
	for(int i=0;i<n;i++)
	{
		while(j&&s[i]!=t[j])j=nxt[j-1];
		if(s[i]==t[j])j++;
		if(j==m)return i-m+1;
	}
	return -1;
}

Rabin–Karp 算法（Hash）

int RK(string s,string t)
{
	int n=s.size(),m=t.size();
	if(n<m)return -1;
	ull h1=0,h2=0,p=Pow(base,m-1);
	for(int i=0;i<m;i++)
	{
		h1=h1*base+s[i];
		h2=h2*base+t[i];
	}
	s+='$';
	for(int i=0;i<=n-m;i++)
	{
		if(h1==h2&&s.substr(i,m)==t)return i;
		h1=(h1-s[i]*p)*base+s[i+m];
	}
	return -1;
}

例题

洛谷 P3375 【模板】KMP

洛谷 P3375 【模板】KMP

给定两个字符串 $s_1$ 和 $s_2$，求出 $s_2$ 在 $s_1$ 中所有出现的位置，以及 next 数组。

#include <bits/stdc++.h>
using namespace std;

const int N=1000005;
int nxt[N];
void kmp(string s,string t)
{
	int n=s.size(),m=t.size();
	for(int i=1;i<m;i++)
	{
		int j=nxt[i-1];
		while(j&&t[i]!=t[j])j=nxt[j-1];
		if(t[i]==t[j])j++;
		nxt[i]=j;
	}
	int j=0;
	for(int i=0;i<n;i++)
	{
		while(j&&s[i]!=t[j])j=nxt[j-1];
		if(s[i]==t[j])j++;
		if(j==m)cout<<i-m+2<<'\n';
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string s,t;
	cin>>s>>t;
	kmp(s,t);
	for(int i=0;i<t.size();i++)
	{
		cout<<nxt[i]<<' ';
	}
	return 0;
}