题解：P3618 误会

原题链接

• 洛谷 P3618 误会

题意简述

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

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

解题思路

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

1. 当 $i<m$ 时，字符串长度不足，无法替换，所以 $f_i=1$。
2. 若 $s[i-m:i-1]=t$，可以选择替换 $s[i-m:i-1]$，但要求替换前的部分不能重叠。因此可以增加方案数 $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-1]=t \\ f_{i-1} & \text{else} \end{cases}$$

利用 KMP 或 Rabin–Karp 等字符串匹配算法，可以单次 $O(1)$ 判断 $s[i-m:i-1]=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;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;
		f[0]=1;
		for(int i=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 算法（Hash）

#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;
}