后缀自动机乱做
HJWJBSR
posted @ 2015年8月26日 23:41
in 专题
, 608 阅读
最近看了SAM课件+论文+博客
基本懂是什么sxbk东西了，有几个主要性质：一个状态所代表的子串互为后缀，并且长度连续；有一个right集合是这个子串出现的位置集合；当前状态的parent状态也是当前状态的子串的后缀，并且其right集合包含了当前状态的right集合；当前状态的最长长度已经处理出来了就是val，而最短长度就是BFS一遍可以得到（maya明明这个就是suf的val+1的所以不用求了）；suf可以建成一棵树；right集合可以O(S)求最大最小值或者元素个数，这些都要先把suf树上的叶子节点也就是所有前缀所代表的状态设个初值然后就可以往上传值，并且两个节点的right集合要不就交集为空要不就一个为另外一个的祖先，而求出这个集合可以用启发式合并。
然后背了下模板，还要学下怎么建后缀数组，准备把cls课件还有论文上面的题目写掉一些。
SPOJ LCS：
求两个子串的最长公共子串
将其中一个的SAM建出来，另外一个在上面跑一遍，同时记录跑完当前字符之后当前的状态以及当前匹配长度，这东西之所以不能直接当成val是因为有可能比val小，于是每往下走的时候就val++，当当前匹配不了时就suf走，然而由性质当前的长度肯定大于suf的长度所以往回走的时候长度又要变成val。
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 | #include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;#define N 250050#define M 26char b[N];struct State { State *suf,*go[M];int val; State(): val(0),suf(0) {memset(go,0,sizeof(go));} } *root,*last,*cur,statePool[N*2],*now;int ans,t;void extend(int w) { State *p=last,*np=cur++; np->val=p->val+1; while (p&&!p->go[w]) p->go[w]=np,p=p->suf; if (!p) np->suf=root;else { State *q=p->go[w]; if (q->val==p->val+1) np->suf=q;else { State *nq=cur++; memcpy(nq->go,q->go,sizeof q->go); nq->val=p->val+1; nq->suf=q->suf; q->suf=np->suf=nq; while (p&&p->go[w]==q) p->go[w]=nq,p=p->suf; } } last=np; }int main() { scanf("%s",b); cur=statePool;root=last=cur++; for (char* i=b;*i;i++) extend(*i-'a'); scanf("%s",b); t=0;now=root; for (char* i=b;*i;i++) if (now->go[*i-'a']) now=now->go[*i-'a'],ans=max(ans,++t);else { while (now&&!now->go[*i-'a']) now=now->suf; if (now==NULL) now=root,t=0;else ans=max(ans,t=now->val+1),now=now->go[*i-'a']; } cout <<ans<<endl; return 0; } |
SPOJ LCS2：
给10个串要求最大匹配大小
当然也是求出第一个串的SAM，然后每个串在上面跑一遍，每跑一遍每个节点记录当前跑出来的最长匹配是多少，并且这个东西可以传给suf的，这样跑10遍，每个点每次跑出的答案要取最小值，所有点的最小值还要取个最大值就是答案。
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 | #include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;#define N 200050#define M 26char b[N];struct State { State *par,*go[M],*ne;int val,t[12],ma; State(): ne(0),par(0) {memset(go,0,sizeof(go));memset(t,0,sizeof(t));} } *root,*last,statePool[N],*cur,*fi[N];int st=0,ans=0,len;inline State* Line(int x) {cur->val=x;cur->ne=fi[x];fi[x]=cur;return cur++;}void extend(int w) { State *p=last,*np=Line(p->val+1); while (p&&!p->go[w]) p->go[w]=np,p=p->par; if (!p) np->par=root;else { State *q=p->go[w]; if (q->val==p->val+1) np->par=q;else { State *nq=Line(p->val+1); memcpy(nq->go,q->go,sizeof q->go); nq->par=q->par; q->par=np->par=nq; while (p&&p->go[w]==q) p->go[w]=nq,p=p->par; } } last=np; }int main() { scanf("%s",b);len=strlen(b); cur=statePool;last=root=Line(0); for (char *i=b;*i;i++) extend(*i-'a'); while (st++,scanf("%s",b)!=EOF) { State* now=root;int s=0; for (char *i=b;*i;i++) { int k=*i-'a'; while (now&&!now->go[k]) now=now->par,s=now?now->val:0; if (!now) now=root,s=0;else now=now->go[k],now->t[st]=max(now->t[st],++s); } } for (int i=len;i>=1;i--) for (State* j=fi[i];j;j=j->ne) { int l=i; for (int k=1;k<st;k++) { l=min(l,j->t[k]); if (j->par) j->par->t[k]=max(j->par->t[k],j->t[k]); } ans=max(ans,l); } cout <<ans<<endl; return 0; } |
SPOJ SUBLEX：
求一个长为n(n<=9w)串的去重的子串集合中的第k(k∈int)大的串并输出，q(q<=500)组询问
还是建出SAM，然后处理出每个状态的可达子串有多少个，这个东西可以拓扑排序之后算一下就好了。然后将询问排序，从root出发依次处理每个询问，同时枚举当前状态的每个转移计算加上这个转移的子串数后是否超过答案，是则到下一个转移，否则进入这个转移。这题时限还只有0.2s左右，还好不卡int（虽然不知道能不能卡），T了好几发删掉了long long才勉强过，SPOJ卡时卡的sxbk。话说一开始这题没看样例以为没有去重的。这样的话每个状态的所代表的子串个数就是right集大小*（最长子串长度-最短子串长度），这样不加long long能过就sxbk了。
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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 | #include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;#define N 180050#define M 26#define fr first#define sc secondstruct State {State *go[M],*suf,*ne;int val,t,wz;};State *root,*last,*cur,statePool[N],*fi[N],*Stack[N];int st,len,m,ans[M*20][2],sta[N];pair <int,int> qu[M*20];char b[N];inline int Read() { int x=0;char y; do y=getchar(); while (y<'0'||y>'9'); do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9'); return x; }inline void Line(State* y,ll x) {y->val=x;y->ne=fi[x];fi[x]=y;}void extend(int w) { State *p=last,*np=cur;Line(cur++,p->val+1); while (p&&!p->go[w]) p->go[w]=np,p=p->suf; if (!p) np->suf=root;else { State *q=p->go[w]; if (q->val==p->val+1) np->suf=q;else { State *nq=cur;Line(cur++,(p->val)+1); memcpy(nq->go, q->go, sizeof q->go); nq->suf=q->suf;q->suf=np->suf=nq; while (p&&p->go[w]==q) p->go[w]=nq,p=p->suf; } } last=np; }void Right() { State* now=root;int l=0; for (char *i=b;*i;i++) { int k=*i-'a'; if (now->go[k]) now=now->go[k];else { while (now&&!now->go[k]) now=now->suf; if (!now) now=root;else now=now->go[k]; } now->wz=l++; } for (int i=len;i>=1;i--) for (State* j=fi[i];j;j=j->ne) j->suf->wz=j->wz,j->t=1; for (int i=len;i>=0;i--) for (State* j=fi[i];j;j=j->ne) for (int k=0;k<M;k++) if (j->go[k]) j->t+=j->go[k]->t; }inline void Update(int x,int y,int z) {ans[z][1]=x;ans[z][0]=x-y+1;}void Solve() { m=Read(); for (int i=1;i<=m;i++) qu[i].fr=Read(),qu[i].sc=i; sort(qu+1,qu+m+1);int ri=1,i=1;ll now=0; Stack[1]=root;sta[1]=0; while (i<=m) { if (!Stack[ri]->go[sta[ri]]) sta[ri]++;else if (now+Stack[ri]->go[sta[ri]]->t<qu[i].fr) now+=Stack[ri]->go[sta[ri]]->t,sta[ri]++;else if (now+1==qu[i].fr) Update(Stack[ri]->go[sta[ri]]->wz,ri,qu[i++].sc);else now++,Stack[ri+1]=Stack[ri]->go[sta[ri]],sta[++ri]=0; while (ri&&sta[ri]==26) sta[--ri]++; } }int main() { scanf("%s",b);len=strlen(b); cur=statePool;st=-1;Line(cur,0);last=root=cur++; for (char *i=b;*i;i++) extend(*i-'a'); Right();Solve(); for (int i=1;i<=m;i++) { for (int j=ans[i][0];j<=ans[i][1];j++) putchar(b[j]); printf("\n"); } return 0; } |
SPOJ NSUBSTR
求字符串中每个长度的相同子串最多有多少，n<=25w
直接求right集合大小，而这个大小是可以更新1~val的ans的，所以对于每个节点直接更新val的ans，最后再从后往前扫一遍用长的ans更新短的ans
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 | #include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;#define N 250050#define M 26struct State {State *suf,*go[M],*ne;int val,ri;};State *root,*last,*cur,statePool[N*2],*fi[N];int len,ans[N];char b[N];inline State* Line(int x) {cur->ne=fi[x];cur->val=x;fi[x]=cur;return cur++;}void extend(int w) { State *p=last,*np=Line(p->val+1); while (p&&!p->go[w]) p->go[w]=np,p=p->suf; if (!p) np->suf=root;else { State *q=p->go[w]; if (q->val==p->val+1) np->suf=q;else { State *nq=Line(p->val+1); memcpy(nq->go,q->go,sizeof q->go); nq->suf=q->suf; q->suf=np->suf=nq; while (p&&p->go[w]==q) p->go[w]=nq,p=p->suf; } } last=np; }void Right() { State* now=root; for (char *i=b;*i;i++) { int k=*i-'a'; while (now&&!now->go[k]) now=now->suf; now=now->go[k]; now->ri++; } for (int i=len;i>=1;i--) for (now=fi[i];now;now=now->ne) now->suf->ri+=now->ri; }int main() { scanf("%s",b);len=strlen(b); cur=statePool;root=last=Line(0); for (char* i=b;*i;i++) extend(*i-'a'); Right(); for (;root!=cur;root++) ans[root->val]=max(ans[root->val],root->ri); for (int i=len-1;i>=1;i--) ans[i]=max(ans[i+1],ans[i]); for (int i=1;i<=len;i++) printf("%d\n",ans[i]); return 0; } |
SPOJ NSUBSTR2
动态加字符，同时给定一个串并且询问这个串在母串中出现几次。强制在线
如果没有修改就是直接处理出每个点的right集合大小。这样也差不多，反正每个点要求出自己子树内的叶子节点个数，就可以上LCT了。在建图过程中不会对suf树造成太大影响，只要处理下nq、q还有np的情况就好了。
然而SPOJ卡时间卡的实在sxbk，我硬是把所有能想到的优化都加上了还不能过，最后还是把每次询问的结点Splay一下才过了= =
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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | #include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;#define N 160050#define M 26struct State {State *suf,*go[M];int val,t;};State *root,*last,statePool[N],*cur;int st,fa[N],rf[N],c[N][2],ad[N],t[N],A,B,m,ans;bool fz[N],d[N];char b[N];inline void fzj(int x) { if (!x||!fz[x]) return; swap(c[x][0],c[x][1]); fz[c[x][0]]=!fz[c[x][0]];fz[c[x][1]]=!fz[c[x][1]]; fz[x]=fz[0]=0; }inline void adj(int x) { if (!x||!ad[x]) return; t[x]+=ad[x];ad[c[x][0]]+=ad[x];ad[c[x][1]]+=ad[x]; ad[x]=ad[0]=0; }inline void Rotate(int x) { int i=fa[x],j=fa[i],k=c[i][0]==x; if (j) c[j][c[j][1]==i]=x;else rf[x]=rf[i],rf[i]=0; if (c[x][k]) fa[c[x][k]]=i; c[i][!k]=c[x][k];fa[i]=x; c[x][k]=i;fa[x]=j; }void Up(int x) {if (fa[x]) Up(fa[x]);fzj(x);adj(x);}void Splay(int x) { Up(x); while (fa[x]) { if (fa[fa[x]]) Rotate(c[fa[fa[x]]][0]==fa[x]^c[fa[x]][0]==x?x:fa[x]); Rotate(x); } }void Access(int x) { int i=0; while (x) { Splay(x); rf[c[x][1]]=fa[i]=x; fa[c[x][1]]=rf[i]=0; c[x][1]=i;i=x;x=rf[x]; } }void Delete(int x,int y) { Splay(x); if (rf[x]==y) rf[x]=0;else Splay(y),c[y][1]=fa[x]=0; }void extend(int w) { State *p=last,*np=cur++;np->t=++st; np->val=p->val+1; while (p&&!p->go[w]) p->go[w]=np,p=p->suf; if (!p) np->suf=root;else { State *q=p->go[w]; if (q->val==p->val+1) np->suf=q;else { State *nq=cur++;nq->t=++st; memcpy(nq->go,q->go,sizeof q->go); Delete(q->t,q->suf->t);t[st]=t[q->t]; nq->val=p->val+1; nq->suf=q->suf; q->suf=np->suf=nq; rf[q->t]=st;rf[st]=nq->suf->t; while (p&&p->go[w]==q) p->go[w]=nq,p=p->suf; } } last=np;rf[np->t]=np->suf->t; Access(np->t);Splay(np->t);ad[np->t]=1;adj(np->t); }int main() { scanf("%s",b); cur=statePool;root=last=cur++;root->t=st=1; for (char* i=b;*i;i++) extend(*i-'a'); cin >>m>>A>>B; while (m--) { scanf("%s",b);State* now=root;ans=0; for (char* i=b;*i;i++) if (!now->go[*i-'a']) {ans=-1;break;}else now=now->go[*i-'a']; ans=ans?0:(Splay(now->t),t[now->t]); printf("%d\n",ans); extend((A*ans+B)%26); } return 0; } |
BZOJ2555
跟上题基本上一样= =
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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 | #include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;#define N 3000050#define M 26struct State {State *suf,*go[M];int val,t;};State *root,*last,statePool[N],*cur;int st,fa[N],rf[N],c[N][2],ad[N],t[N],A,B,m,ans,n,mask;bool fz[N],d[N];char b[N],f[M];inline void fzj(int x) { if (!x||!fz[x]) return; swap(c[x][0],c[x][1]); fz[c[x][0]]=!fz[c[x][0]];fz[c[x][1]]=!fz[c[x][1]]; fz[x]=fz[0]=0; }inline void adj(int x) { if (!x||!ad[x]) return; t[x]+=ad[x];ad[c[x][0]]+=ad[x];ad[c[x][1]]+=ad[x]; ad[x]=ad[0]=0; }inline void Rotate(int x) { int i=fa[x],j=fa[i],k=c[i][0]==x; if (j) c[j][c[j][1]==i]=x;else rf[x]=rf[i],rf[i]=0; if (c[x][k]) fa[c[x][k]]=i; c[i][!k]=c[x][k];fa[i]=x; c[x][k]=i;fa[x]=j; }void Up(int x) {if (fa[x]) Up(fa[x]);fzj(x);adj(x);}void Splay(int x) { Up(x); while (fa[x]) { if (fa[fa[x]]) Rotate(c[fa[fa[x]]][0]==fa[x]^c[fa[x]][0]==x?x:fa[x]); Rotate(x); } }void Access(int x) { int i=0; while (x) { Splay(x); rf[c[x][1]]=fa[i]=x; fa[c[x][1]]=rf[i]=0; c[x][1]=i;i=x;x=rf[x]; } }void Delete(int x,int y) { Splay(x); if (rf[x]==y) rf[x]=0;else Splay(y),c[y][1]=fa[x]=0; }void extend(int w) { State *p=last,*np=cur++;np->t=++st; np->val=p->val+1; while (p&&!p->go[w]) p->go[w]=np,p=p->suf; if (!p) np->suf=root;else { State *q=p->go[w]; if (q->val==p->val+1) np->suf=q;else { State *nq=cur++;nq->t=++st; memcpy(nq->go,q->go,sizeof q->go); Delete(q->t,q->suf->t);t[st]=t[q->t]; nq->val=p->val+1; nq->suf=q->suf; q->suf=np->suf=nq; rf[q->t]=st;rf[st]=nq->suf->t; while (p&&p->go[w]==q) p->go[w]=nq,p=p->suf; } } last=np;rf[np->t]=np->suf->t; Access(np->t);Splay(np->t);ad[np->t]=1;adj(np->t); }int main() { scanf("%d%s",&m,b); cur=statePool;root=last=cur++;root->t=st=1; for (char* i=b;*i;i++) extend(*i-'A'); while (m--) { scanf("%s%s",f,b); for (int i=0,len=strlen(b),Mask=mask;i<len;i++) Mask=(Mask*131+i)%len,swap(b[i],b[Mask]); if (f[0]=='A') for (char* i=b;*i;i++) extend(*i-'A');else { State* now=root;ans=0; for (char* i=b;*i;i++) if (!now->go[*i-'A']) {ans=-1;break;}else now=now->go[*i-'A']; ans=ans?0:(Splay(now->t),t[now->t]); printf("%d\n",ans);mask^=ans; } } return 0; } |
BZOJ 3676
题面：给定一个串，一个回文子串的权值是它的长度*它的出现次数，要求求出串中最大权值。|S|<=30w
题解：因为是在Keavil论文上看到这道题，但是按他的思路一直都没想出来怎么做，主要是一个状态可以是很多子串，所以不能直接更新出现次数。后来知道这题好像有至少三种写法真是sxbk，回文自动机的写法以后补，还有一个好神的hash和hzwer的SAM写法。后面两种主要都是有一个性质就是一个串中的不同的回文子串个数是O(n)的，感觉果然是manacher没学好= =，所以就可以直接在manacher过程中搞。hash解法好像是在manacher过程中把当前这个串hash然后建出一棵树，然后好像就可以搞了。SAM就是manacher的时候用当前回文子串倍增找到这个串所在答案，查询right集合大小更新答案。搞懂之后还调了好久，一开始naive没看空间限制，后面重新用数组写一遍才勉强卡过限制，结果还是写挂了好多地方调了好久= =，果然人太弱了。
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 80 81 82 | #include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>using namespace std;#define N 300050#define M 26#define ll long longint fi[N],ne[N*2],val[N*2],go[N*2][M],suf[N*2][19];ll ans=0;int pre[N],p[N*2],b[N*2],n,m,root,last,cur,ri[N*2];char c[N];void extend(int w,int x) { int p=last,np=cur++; val[np]=val[p]+1; ne[np]=fi[val[np]];fi[val[np]]=np; while (p&&!go[p][w]) go[p][w]=np,p=suf[p][0]; if (!p) suf[np][0]=root;else { int q=go[p][w]; if (val[q]==val[p]+1) suf[np][0]=q;else { int nq=cur++; val[nq]=val[p]+1; ne[nq]=fi[val[nq]];fi[val[nq]]=nq; memcpy(go[nq],go[q],sizeof go[q]); suf[nq][0]=suf[q][0]; suf[q][0]=suf[np][0]=nq; while (p&&go[p][w]==q) go[p][w]=nq,p=suf[p][0]; } } ri[last=pre[x]=np]=1; }void Set_up() { for (int i=n;i>=1;i--) for (int j=fi[i];j;j=ne[j]) ri[suf[j][0]]+=ri[j]; for (int i=1;i<=n;i++) for (int j=fi[i];j;j=ne[j]) for (int k=0;k<18&&suf[suf[j][k]][k];k++) suf[j][k+1]=suf[suf[j][k]][k]; }inline ll max(ll x,ll y) {return x>y?x:y;}void Query(int x,int y) { if (x>y) return; int t=pre[y]; for (int i=18;i>=0;i--) if (suf[t][i]&&val[suf[t][i]]>=y-x+1) t=suf[t][i]; ans=max(ans,(ll)(ri[t])*(y-x+1)); }void Manacher() { int k=0,l=-1; for (int i=0;i<n;i++) b[i*2+1]=c[i]; n*=2;b[n+1]=-1; for (int i=0;i<=n;i++) { if (i<l) p[i]=min(p[k*2-i],l-i+1); while (i-p[i]>=0&&b[i-p[i]]==b[i+p[i]]) Query(i-p[i] >> 1,i+p[i]-1 >> 1),p[i]++; if (i+p[i]-1>l) l=i+p[i]-1,k=i; } }int main() { scanf("%s",c);n=strlen(c); cur=1;last=root=cur++; for (int i=0;i<n;i++) extend(c[i]-'a',i); Set_up();Manacher(); cout <<ans<<endl; return 0; } |
SAM转后缀数组就是标记每个结束状态然后DFS一遍SAM就很愉快了。
评论 (0)
