字符串匹配

参考资料

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

KMP 算法

int kmp(string s,string t)
{
	int n=s.size(),m=t.size();
	for(int i=1,j=0;i<m;i++)
	{
		while(j&&t[i]!=t[j])j=nxt[j-1];
		if(t[i]==t[j])j++;
		nxt[i]=j;
	}
	for(int i=0,j=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 算法

详见 字符串哈希。

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

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

Code (1)

#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,j=0;i<m;i++)
	{
		while(j&&t[i]!=t[j])j=nxt[j-1];
		if(t[i]==t[j])j++;
		nxt[i]=j;
	}
	for(int i=0,j=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;
}

洛谷 P3618 误会

给定 $T$ 组数据，每组包含一个长度为 $n$ 的字符串 $s$ 和一个长度为 $m$ 的字符串 $t$。

可以将 $s$ 中任意与 $t$ 相同的子串替换为 *，求有多少种不同的替换方案。

Solution

参考资料

• 字符串匹配 - OI Wiki
• 前缀函数与 KMP 算法 - OI Wiki
• Knuth–Morris–Pratt algorithm - Wikipedia
• Rabin–Karp algorithm - Wikipedia

题意简述

给定 $T$ 组数据，每组包含一个长度为 $n$ 的字符串 $s$ 和一个长度为 $m$ 的字符串 $t$。

可以将 $s$ 中任意与 $t$ 相同的子串替换为 *，求有多少种不同的替换方案。

解题思路

定义 $f_i$ 表示在 $s[0:i]$ 范围内进行替换的方案数，分类讨论：

1. 当 $i<m$ 时，字符串长度不足，无法替换，所以 $f_i=1$。
2. 若 $s[i-m:i]=t$，可以选择替换 $s[i-m:i]$，但要求替换前的部分不能重叠。因此可以增加方案数 $f_{i-m}$，所以 $f_i\gets f_{i-1}+f_{i-m}$。
3. 否则，只能选择不替换，所以 $f_i\gets f_{i-1}$。

列出状态转移方程：

$$f_i= \begin{cases} 1 & i<m \\ f_{i-1}+f_{i-m} & s[i-m:i]=t \\ f_{i-1} & \text{otherwise} \end{cases}$$

利用 KMP 算法 或 Rabin–Karp 算法（Hash）等字符串匹配算法，可以单次 $O(1)$ 判断 $s[i-m:i]=t$ 是否成立。

参考代码

KMP 算法

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

const int mod=1e9+7;
const int N=100005;
int nxt[N],f[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		string s,t;
		cin>>s>>t;
		int n=s.size(),m=t.size();
		for(int i=1,j=0;i<m;i++)
		{
			while(j&&t[i]!=t[j])j=nxt[j-1];
			if(t[i]==t[j])j++;
			nxt[i]=j;
		}
		f[0]=1;
		for(int i=0,j=0;i<n;i++)
		{
			while(j&&s[i]!=t[j])j=nxt[j-1];
			if(s[i]==t[j])j++;
			f[i+1]=i<m?1:f[i]%mod;
			if(j==m)f[i+1]=(f[i+1]+f[i-m+1])%mod;
		}
		cout<<"Case #"<<_<<": "<<f[n]<<'\n';
	}
	return 0;
}

Rabin–Karp 算法

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

using ull=unsigned long long;
const int base=131;
const int mod=1e9+7;
const int N=100005;
ull Pow(ull a,ull b)
{
	ull res=1;
	while(b)
	{
		if(b&1)res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
int f[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		string s,t;
		cin>>s>>t;
		int n=s.size(),m=t.size();
		ull h1=0,h2=0,p=Pow(base,m-1);
		for(int i=0;i<m;i++)
		{
			f[i]=1;
			h1=h1*base+s[i];
			h2=h2*base+t[i];
		}
		s+='$';
		for(int i=m;i<=n;i++)
		{
			f[i]=f[i-1]%mod;
			if(h1==h2)f[i]=(f[i]+f[i-m])%mod;
			h1=(h1-s[i-m]*p)*base+s[i];
		}
		cout<<"Case #"<<_<<": "<<f[n]<<'\n';
	}
	return 0;
}