题解 P3763 【[TJOI2017]DNA】

丝毫没有羞耻之心地发一波跑了2300+s的~~狗屎~~代码 # 用的字符串哈希 说真的以前没有接触过哈希这玩意儿 Claris~~（是的本周我第三次cue他了）~~今天讲了几分钟哈希就拿出了这道例题 ~~蒟蒻瑟瑟发抖~~ 有些东西真的讲不太清，请见谅 ```cpp //hash(l,r)=hash(1,r)-hash(1,l-1)*seed^(r-l+1) #include<bits/stdc++.h> using namespace std; typedef unsigned long long ULL;//自然溢出，这道题没被卡哇哈哈 const int N=100000+3,D=233; int n,m,T,ans; char a[N],b[N]; ULL p[N],f[N],g[N]; inline ULL ask(ULL*f,int l,int r){//[l,r]的哈希值 return f[r]-f[l-1]*p[r-l+1]; } inline int lcp(int x,int y,int r){ int l=1,mid,t=0; while(l<=r){//二分查找（这个东西可以让一个机房的人吵起来） mid=(l+r)>>1; if(ask(f,x,x+mid-1)==ask(g,y,y+mid-1)){//如果这一段是相等的 t=mid;//标记长度 l=mid+1;//l右移 } else r=mid-1;//不相等就左移 } return t;//返回长度 } inline bool check(int x){ int r=x+m-1,y=1;//r：S0的尾；y:S的头 for(int i=0;i<3;++i){//3次容错 int t=lcp(x,y,m-y+1);//相同的长度 // m-y+1 x+=t+1;//不相等的那个要跳过 y+=t+1; if(y>m)return 1;//如果最终长度能>m,就匹配成功 } return ask(f,x,r)==ask(g,y,m); } int main(){ scanf("%d",&T); while(T--){ scanf("%s%s",a+1,b+1); n=strlen(a+1); m=strlen(b+1); if(n<m){//不解释 printf("0\n"); continue; } p[0]=1; for(int i=1;i<=n;++i)p[i]=p[i-1]*D;//预处理 for(int i=1;i<=n;++i)f[i]=f[i-1]*D+a[i];//哈希值 for(int i=1;i<=m;++i)g[i]=g[i-1]*D+b[i]; ans=0; for(int i=1;i+m-1<=n;++i)//枚举相同字符串的头 if(check(i))ans++; printf("%d\n",ans); } return 0; } ``` 我真的觉得这个跑得好慢啊QAQ ~~可是别的我也不会写了QWQ~~