题解 p3618 【误会】

#define ll long long
#define ull unsigned long long
using namespace std;
const int p=313;
int v=1,T,n,m,a[2000000];
ull power[2000000],sum[2000000],f[200000],t;
char s1[200000],s2[200000];
int (){
    scanf("%d",&T);
    power[0]=1;
    for (int i=1;i<=100001;i++) power[i]=power[i-1]*p;
    while (v<=T){
        scanf("%sn%s",s1+1,s2+1);
        memset(f,0,sizeof(f));
        n=strlen(s1+1);m=strlen(s2+1);t=0;
        for (int i=1;i<=n;i++) 
            sum[i]=sum[i-1]*p+s1[i]-96;
        for (int i=1;i<=m;i++)
            t=t*p+s2[i]-96;
        f[0]=1;
        for (int i=1;i<=n;i++)
            if (t==sum[i]-sum[i-m]*power[m])
                f[i]=(f[i-1]+f[i-m])%1000000007;
            else f[i]=f[i-1];
        printf("Case #%d: %dn",v,f[n]);
        v++;
    }
}