bzoj4892 [Tjoi2017]dna SAM 后缀自动机

bzoj4892 [Tjoi2017]dna SAM 后缀自动机

​​ 当年SA的做法在bzoj上被卡常成sb。。 Description

加里敦大学的生物研究所，发现了决定人喜不喜欢吃藕的基因序列S,有这个序列的碱基序列就会表现出喜欢吃藕的 性状，但是研究人员发现对碱基序列S,任意修改其中不超过3个碱基，依然能够表现出吃藕的性状。现在研究人员 想知道这个基因在DNA链S0上的位置。所以你需要统计在一个表现出吃藕性状的人的DNA序列S0上，有多少个连续子 串可能是该基因，即有多少个S0的连续子串修改小于等于三个字母能够变成S。

Input

第一行有一个数T,表示有几组数据 每组数据第一行一个长度不超过10^5的碱基序列S0 每组数据第二行一个长度不超过10^5的吃藕基因序列S

Output

共T行，第i行表示第i组数据中，在S0中有多少个与S等长的连续子串可能是表现吃藕性状的碱基序列

Sample Input

1 ATCGCCCTA CTTCA Sample Output

2 HINT

Source

建出sam之后直接利用Par树的性质dfs一下即可 设dfs(x,l,wr)分别表示我当前在x节点我匹配长度是l 修改了wr次 如果我到达一个节点发现 长度匹配到了 那么就加上这个节点所能表示的字符串数量

icefox好强啊orz 常数好小啊

#include#include#include#include#define N 200020 using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f;}int cnt,len[N],fa[N],ch[N][4],c[N>>1],size[N],leth,w[255],last,rk[N],root,ans;inline void insert1(int x){ static int np,q,nq,p; np=++cnt,p=last;len[np]=len[p]+1; for (;p&&!ch[p][x];p=fa[p]) ch[p][x]=np; if (!p) fa[np]=root;else{ q=ch[p][x];if (len[p]+1==len[q]) fa[np]=q;else{ nq=++cnt;memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q];len[nq]=len[p]+1; fa[q]=fa[np]=nq;for (;p&&ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }last=np;size[np]=1;}char s[N>>1];inline void dfs(int x,int l,int wr){ if(l==leth) {ans+=size[x];return;} int nx=w[s[l+1]]; for (int i=0;i<4;++i){ if(!ch[x][i]) continue; if (i==nx) dfs(ch[x][i],l+1,wr);else if (wr<3) dfs(ch[x][i],l+1,wr+1); }}int main(){ freopen("bzoj4892.in","r",stdin); int T=read();w['A']=0;w['T']=1;w['C']=2;w['G']=3; while(T--){leth=0; memset(size,0,sizeof(size));memset(ch,0,sizeof(ch));root=cnt=last=1;memset(c,0,sizeof(c)); scanf("%s",s+1);leth=strlen(s+1); for (int i=1;i<=leth;++i) insert1(w[s[i]]); for (int i=1;i<=cnt;++i) ++c[len[i]]; for (int i=1;i<=leth;++i) c[i]+=c[i-1]; for (int i=1;i<=cnt;++i) rk[c[len[i]]--]=i;leth=0; for (int i=cnt;i;--i) {int x=rk[i];size[fa[x]]+=size[x];} scanf("%s",s+1);leth=strlen(s+1); ans=0;dfs(1,0,0);printf("%d\n",ans); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。