Skip to main content

字符串匹配

参考资料​

简介​

字符串匹配（String Matching）求模式串 tt 在文本串 ss 中的所有出现位置。朴素枚举为 O(nm)O(nm)。KMP 预处理模式串的前缀函数 nxt\mathrm{nxt}，失配时跳到最长相等前后缀处继续，做到 O(n+m)O(n+m)。Rabin–Karp 用滚动哈希逐位比较子串，平均 O(n+m)O(n+m)。

KMP 算法​

280 Bcpp
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 算法​

详见 字符串哈希。

296 Bcpp
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

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

洛谷 P3618 误会

给定 TT 组数据，每组包含一个长度为 nn 的字符串 ss 和一个长度为 mm 的字符串 tt。

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