「Luogu P3618」误会 解题报告

题面

解题思路

$\mathtt{DP+hash}$

分析

正解不是很是难想，由于是计数类问题，应该就想到 $DP$，又由于字符串，即可用字符串 $hash$ 解决

记原句为 $A$ 串，长度为 $la$；听到的话为 $B$ 串，长度为 $lb$

考虑怎么转移，分情况讨论：

· 如果在 $A$ 串位置 $i$ 能匹配上 $B$ 串，显然，替换是一种，不替换也是一种选择，直接相加 $\to$ f[i]=f[i-lb]+f[i-1]

· 反之，不能匹配，此时只有不替换一种选择，直接转移 $\to$ f[i]=f[i-1]

对于 $hash$，使用 $unsigned\ long\ long$ 的自然溢出即可，（默认字符串 $hash$ 都会

Warning

$f_{0-lb}$ 都应初始为 $1$

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define ull unsigned LL
#define N 100003
using namespace std;
const int base=1000000007;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,m,la,lb,t,f[N];
ull s[N],sum,bit[N];
char a[N],b[N];
inline int dec(rint x){return(x>=base)?x-base:x;}
int main()
{
    rint i,k;m=read(),bit[0]=1,t=f[0]=1;
    for(k=1;k<=m;k++) {
        scanf("%s%s",a+1,b+1),la=strlen(a+1),lb=strlen(b+1),sum=0;
        for(i=1;i<=la;i++) s[i]=s[i-1]*base+a[i]-'0';//得到A串的前缀hash
        while(t<=lb) bit[t]=bit[t-1]*base,++t;//base^t
        for(i=1;i<=lb;i++) sum=sum*base+b[i]-'0',f[i]=1;//计算B串的hash值&初始化
        for(i=lb;i<=la;i++) {
            if(sum==s[i]-s[i-lb]*bit[lb]) f[i]=f[i-lb];//可以替换
            else f[i]=0;f[i]=dec(f[i]+f[i-1]);
        }
        printf("Case #%d: %d\n",k,f[la]);
    }
    return 0;
}