题解 P3618 【误会】

· · 题解

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]);
    }
}