自动搬运

查看原文

来自洛谷，原作者为

	Ajwallet 厌倦追寻，一觅即中

搬运于2025-08-24 21:50:49，当前版本为作者最后更新于2019-12-06 19:38:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$Hyperlink$

https://www.luogu.com.cn/problem/P3618

$Description$

有$T$组数据

每组数据给定两个串$a,b$

对于$a$的每一个子串$S_a$，若$S_a=b$，则可以用$*$替代

问一共有多少种替代方法（不替代也算为一种）

数据范围：$n\leq 10^5$

$Solution$

KMP它能不香吗？

首先对于$a,b$两串，求出$b$串在$a$串中的所有匹配位置

刚开始是想着用组合计数的方法算方案数。。。（毕竟看到了模数）

然后看了题解发现可以用$dp$

套上去就切了。。。

设$f[i]$表示做到$i$的方案数

初始状态：$f[0]=1$

如果$i-m+1$是一个可以匹配的位置，则$f[i]=f[i-1]+f[i-m]$

否则$f[i]=f[i-1]$

时间复杂度$O(T(n+m))$

$Code$

#include<cstdio>
#include<cstring>
#define N 100010
#define mod 1000000007
using namespace std;char a[N],b[N];
int n,m,next[N],j,t,nt;
long long f[N];
bool v[N];
int main()
{
	scanf("%d",&t);
	while(t--)
	{	
	    scanf("%s%s",a+1,b+1);
	    n=strlen(a+1);m=strlen(b+1);
	    memset(next,0,sizeof(next));
	    memset(v,0,sizeof(v));
	    memset(f,0,sizeof(f));
	    j=0;
		for(register int i=2;i<=m;i++)
		{
			while(j&&b[j+1]!=b[i]) j=next[j];
			if(b[j+1]==b[i]) j++;
			next[i]=j;
		}
		j=0;
		for(register int i=1;i<=n;i++)
		{
			while(j&&b[j+1]!=a[i]) j=next[j];
			if(b[j+1]==a[i]) j++;
			if(j==m) v[i-m+1]=true;
		}
	    f[0]=1;
	    for(register int i=1;i<=n;i++)
	    {
	    	if(v[i-m+1]&&i>=m) (f[i]=f[i-m]+f[i-1])%=mod;
	    	else (f[i]=f[i-1])%=mod;
	    }
	    printf("Case #%d: %lld\n",++nt,f[n]);
	}
}