洛谷 P3763 [TJOI2017]DNA（二分+Hash）
Posted On 2019年1月3日
P3763 [TJOI2017]DNA
对于每个位置，至多跳过3个字符匹配，直接暴力二分求3次lcp即可
|
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 |
#include <iostream> #include <cstdio> #include <cstring> using namespace std; typedef unsigned long long ull; inline int read() { int f=1,k=0;char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=1e5+10,up=1e5; const ull BASE=5; char s[maxn],t[maxn]; int n,m; ull base[maxn],a[maxn],b[maxn]; inline int min(const int a,const int b){return a<b?a:b;} inline ull get(char x){return (x=='A'?0:(x=='T'?1:(x=='C'?2:3)));} inline ull gethash(ull*t,const int l,const int r){return (t[r]-t[l-1])*base[up-l+1];} inline int lcp(const int beg,const int BEG) { int R=min(n-beg+1,m-BEG+1),l=0,r=R,mid; while (l<r) { mid=((l+r)>>1)+1; if (gethash(a,beg,beg+mid-1)!=gethash(b,BEG,BEG+mid-1))r=mid-1;else l=mid; } return l; } inline bool check(const int l) { int now=l,r=now+m-1,cnt=0; while (now<=r&&++cnt<=3) { int R=lcp(now,now-l+1); now+=R+1; if (now>r||(cnt==3&&now+lcp(now,now-l+1)>r))return 1; } return 0; } inline void work() { scanf("%s",s+1);n=strlen(s+1); for (int i=1;i<=n;i++)a[i]=a[i-1]+get(s[i])*base[i]; scanf("%s",t+1);m=strlen(t+1); for (int i=1;i<=m;i++)b[i]=b[i-1]+get(t[i])*base[i]; int ans=0; for (int i=1;i<=n-m+1;i++) if (check(i))++ans; printf("%d\n",ans); } inline void pre() { base[up]=1; for (int i=up-1;i;i--)base[i]=base[i+1]*BASE; } signed main() { pre(); for (int T=read();T;T--)work(); } |
Subscribe
0 评论