题解
题目大意：给两个串，S，T，问S中有多少个子串与T的差异是在3个字符以内的。
这道题解法有很多，像什么SAM，FFT，NTT之类的，然而我只会哈希orz
二分找它们的最长公共前缀，最多能跳3次，没了……
设N为S的长度，M为T的长度
时间复杂度 O((N-M)\times (logM))
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; const int P=131,MAXN=100005; ull hash1[MAXN]; ull hash2[MAXN]; ull Q[MAXN]; int n,len1,len2;string str; int num(char ch){ if(ch=='A')return 0; if(ch=='T')return 1; if(ch=='C')return 2; return 3; } ull ask(int type,int l,int r){ if(type==1)return hash1[r]-hash1[l-1]*Q[r-l+1]; else return hash2[r]-hash2[l-1]*Q[r-l+1]; } int lcp(int x,int y,int r){ int l=1,mid,t=0; while(l<=r){ mid=(l+r)>>1; if(ask(1,x,x+mid-1)==ask(2,y,y+mid-1)){ t=mid; l=mid+1; } else r=mid-1; } return t; } bool check(int x){ int r=x+len2-1,y=1; for(int i=0;i<3;i++){ int t=lcp(x,y,len2-y+1); x+=t+1; y+=t+1; if(y>len2)return 1; } return ask(1,x,r)==ask(2,y,len2); } void solve(){ int ans=0; for(int i=1;i<=len1-len2+1;i++){ if(check(i))ans++; } cout<<ans<<endl; } int main(){ Q[0]=1; for(int i=1;i<=100000;i++)Q[i]=Q[i-1]*P; cin>>n; while(n--){ cin>>str; len1=str.length(); for(int i=0;i<len1;i++){ i+=1; hash1[i]=hash1[i-1]*P+num(str[i-1]); i-=1; } cin>>str; len2=str.length(); for(int i=0;i<len2;i++){ i+=1; hash2[i]=hash2[i-1]*P+num(str[i-1]); i-=1; } solve(); memset(hash1,0,sizeof(hash1)); memset(hash2,0,sizeof(hash2)); } return 0; } |