字符串匹配

参考资料

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

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

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

洛谷 P3618 误会

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

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