首页 > 代码库 > 后缀自动机总结
后缀自动机总结
第一次写一个算法的总结
poj 1509 Glass Beads
题目要求求一个字符串的最小表示，在SAM上面走，可以找到这个字符串的所以字串，这样我们可以把 string str 重复一次，
然后在SAM上面往最小的走 len 步，这样得到的就是题目要求的
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define mod 1000000007#define maxn 20010#define pi acos(-1.0)#define eps 1e-6using namespace std;struct SAM{ SAM *pre,*son[26] ; int len ,g ;}que[maxn],*root,*tail,*b[maxn];int tot ;void add(int c ,int l){ SAM *p = tail,*np=&que[tot++] ; np->len=l;tail=np ; while(p&&p->son[c]==NULL)p->son[c]=np,p=p->pre ; if(p==NULL) np->pre = root ; else { SAM *q = p->son[c] ; if(p->len+1==q->len)np->pre = q ; else { SAM *nq = &que[tot++] ; *nq=*q ; nq->len = p->len+1; np->pre=q->pre=nq; while(p&&p->son[c]==q) p->son[c]=nq,p=p->pre; } }}char str[maxn];void init(int n ){ tot=0; for(int i = 0 ; i < n ;i++) { que[i].g = 0 ; que[i].pre=NULL; memset(que[i].son,0,sizeof(que[i].son)) ; } root=tail=&que[tot++] ;}int solve(int n ){ for( int i = 1 ; i <= n ;i++) { add(str[i-1]-‘a‘,i) ; } for( int i = 1 ; i <= n ;i++) { add(str[i-1]-‘a‘,i+n) ; } SAM *now = &que[0] ; for(int i = 0 ; i < n ;i++) { for(int j = 0 ;j < 26 ;j++) { if(now->son[j] != NULL) { now = now->son[j] ; break ; } } } return now->len ;}int main(){ int m,n,i,j,k; int u,v,c; while(scanf("%d",&n) != EOF) { while(n--) { scanf("%s",str) ; m = strlen(str) ; init(m*2); printf("%d\n",solve(m)-m+1) ; } } return 0 ;}
hdu 4270 Dynamic Lover
题意 ：1.插入一个字符串，2 .询问1-len开头的，长度为len的(如果有的话，没有就是后缀了)，最小子串是谁，3，删除末尾 长为 len 的子串
对于询问，和上面一样，走len步，这里有可能是长度不为len,所以把后缀标记一下就好了。对于 1，直接插入，对于 3，
我们在后缀自动机增加标记 *del，这个指向一个数组。而且它复制出来的节点和它指向地址是一样的，这样删除就只要标记一个就好了。
还有在插入的时候，用pos[i]记录长度为i的字符在SAM位置。删的时候，就从n-len+1删除到n就好了，注意删除后的末尾节点也要改变
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define mod 1000000007#define maxn 300010#define INF 0x3f3f3f3fusing namespace std;struct SAM{ SAM *pre,*son[26] ; int e,id; bool *del; int len ,g; void init() { pre=NULL ; e=0; memset(son,NULL,sizeof(son)) ; }}que[maxn],*root,*tail,*b[maxn];int tot ,tt ;int kk ,n ,cnt,pos[maxn];bool num[maxn];void add(int c ,int l){ que[tot].init(); SAM *p = tail,*np=&que[tot++] ; np->del = &num[tt++]; np->len=np->id=l;tail=np ; pos[l]=tot-1; while(p&&(p->son[c]==NULL||(*p->son[c]->del)))p->son[c]=np,p=p->pre ; if(p==NULL) np->pre = root ; else { SAM *q = p->son[c] ; if(p->len+1==q->len)np->pre = q ; else { SAM *nq = &que[tot++] ; *nq=*q ; nq->len = p->len+1; np->pre=q->pre=nq; while(p&&p->son[c]==q) p->son[c]=nq,p=p->pre; } }}int dfs(SAM *p ,int len){ if(len==kk) return p->id-kk+1 ; if(p->e==cnt) return n-len+1 ; for(int i = 0 ; i < 26 ;i++)if(p->son[i]&&!(*p->son[i]->del)) return dfs(p->son[i],len+1) ;}void Delete(int len ){ for(int i = n-len+1 ; i <= n ;i++)*(que[pos[i]].del)=true; n -= len ; tail = &que[pos[n]];}void init(){ tot=0; tt=0; cnt=0; memset(num,0,sizeof(num)) ; que[tot].init(); root=tail=&que[tot++] ; root->del = &num[tt++] ;}char a[maxn] ;int main(){ int i ,m,k ,j ; int T ,case1=0,len; while(scanf("%s",a) !=EOF) { n = strlen(a) ; init(); for( i = 1 ; i <= n ;i++) add(a[i-1]-‘a‘,i); scanf("%d",&m) ; while(m--) { scanf("%d",&k) ; if(k==1) { scanf("%s",a) ; len=strlen(a) ; for( i = 0 ; i < len ;i++) add(a[i]-‘a‘,++n) ; } else if(k==2) { SAM *p ; cnt++; p = tail ; while(p != NULL &&p != root){ p->e = cnt ; p = p->pre ; } root->e=0; p = root ; scanf("%d",&kk) ; printf("%d\n",dfs(p,0)) ; } else { scanf("%d",&j) ; Delete(j); } } } return 0 ;}
hdu 4416 Good Article Good sentence
题意：给出 string a ，和 string b[] ，询问a一共有多少个不同的子串 不是b[i]的子串
对a建立 SAM,然后经行拓扑排序。然后b[i]去上面匹配，对于节点 p 我们记录所有b[i]中长度最长的匹配，p->g
因为父辈的子串由儿子那里得到，我们从后面开始计算答案，然后把p->g传给父亲。
计算的时候，对于节点 p ，以它为结尾的字串由p->len 个，它和父亲重叠的部分是 p->pre->len ，
和b[i]字串重叠最长p->g ,所以得到合法子串 p->len - max(p->pre->len ,p->g ) ;
注意SAM得到的字串都是不重复的，所以计算出来的就是所以不重复的字串。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define mod 1000000007#define maxn 200010#define INF 0x3f3f3f3fusing namespace std;struct SAM{ SAM *pre,*son[26] ; int len ,g;}que[maxn],*root,*tail,*b[maxn];int tot ;void add(int c ,int l){ SAM *p = tail,*np=&que[tot++] ; np->len=l;tail=np ; while(p&&p->son[c]==NULL)p->son[c]=np,p=p->pre ; if(p==NULL) np->pre = root ; else { SAM *q = p->son[c] ; if(p->len+1==q->len)np->pre = q ; else { SAM *nq = &que[tot++] ; *nq=*q ; nq->len = p->len+1; np->pre=q->pre=nq; while(p&&p->son[c]==q) p->son[c]=nq,p=p->pre; } }}void init(int n ){ tot=0; for( int i = 0 ; i <= n ;i++) { que[i].pre = NULL ; que[i].g=0; memset(que[i].son,0,sizeof(que[i].son)) ; } root=tail=&que[tot++] ;}char a[maxn] ;int C[maxn] ;LL solve(int n ,int m){ memset(C,0,sizeof(C)) ; for(int i = 0 ; i < tot;i++) C[que[i].len]++ ; for(int i = 1 ; i <= n ;i++)C[i] += C[i-1] ; for(int i = 0 ; i < tot ;i++)b[--C[que[i].len]] =&que[i] ; SAM *p ; int tmp,len,i; while(m--) { p = &que[0] ; tmp=0; scanf("%s",a) ; len = strlen(a) ; for( i = 0 ; i < len ;i++) { if(p->son[a[i]-‘a‘]) { tmp++ ; p = p->son[a[i]-‘a‘]; } else { while(p && p->son[a[i]-‘a‘]==NULL) p = p->pre ; if(p==NULL) { tmp=0; p = &que[0] ; } else { tmp = p->len+1; p = p->son[a[i]-‘a‘]; } } p->g = max(p->g,tmp) ; } } LL ans = 0 ; for( i = tot-1 ; i > 0 ;i--) { p = b[i]; if(p->pre){ tmp = max(p->pre->len,p->g); p->pre->g = max(p->pre->g,p->g ) ; } else tmp = p->g ; if(p->len<tmp)tmp=p->len; ans += p->len-tmp ; } return ans;}int main(){ int i , n, m,k ,j ; int T ,case1=0; cin >> T ; while( T--) { scanf("%d",&m) ; scanf("%s",a); n = strlen(a) ; init(n*2); for( i = 1 ; i <= n ;i++) add(a[i-1]-‘a‘,i); printf("Case %d: ",++case1); cout << solve(n,m) << endl; } return 0 ;}
hdu 4622 Reincarnation
题意：给出 string a ,给出l,r区间，询问这个居间不同字串个数
离线，记录 l,下所以的询问 r 。对于不同l ,每次我们都重构SAM
查找的时候，对于节点 p , 以它结尾的有p->len 个子串，和父亲重叠的 p->pre->len
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define mod 1000000007#define maxn 10010#define INF 0x3f3f3f3fusing namespace std;struct SAM{ SAM *pre,*son[26] ; int len ,g ,num; bool vi;}que[maxn],*root,*tail,*b[maxn];int tot ;void add(int c ,int l){ SAM *p = tail,*np=&que[tot++] ; np->len=l;tail=np ; while(p&&p->son[c]==NULL)p->son[c]=np,p=p->pre ; if(p==NULL) np->pre = root ; else { SAM *q = p->son[c] ; if(p->len+1==q->len)np->pre = q ; else { SAM *nq = &que[tot++] ; *nq=*q ; nq->len = p->len+1; np->pre=q->pre=nq; while(p&&p->son[c]==q) p->son[c]=nq,p=p->pre; } }}char str1[10010];void init(int n ){ tot=0; for(int i = 0 ; i <= n ;i++) { memset(que[i].son,0,sizeof(que[i].son)) ; que[i].num = 0 ; que[i].pre=NULL; } root=tail=&que[tot++] ;}int find(){ int ans=0; for(int i =1 ; i < tot;i++) { SAM *p = que[i].pre ; if(p != NULL ) ans += que[i].len-p->len ; else ans += que[i].len ; } return ans;}struct node{ int R,id ; bool operator<(const node&s) const { return R < s.R ; }};vector<node>qe[maxn] ;int ans[maxn];int main(){ int m,n,i,j; int u,v,c,tmp; int T ,len; node a; cin >> T ; while(T--) { scanf("%s",str1+1) ; scanf("%d",&m) ; n = strlen(str1+1) ; for( i =1 ; i <= n ;i++) qe[i].clear(); for( i = 1 ; i <= m ;i++){ scanf("%d%d",&u,&v); a.R =v ; a.id= i ; qe[u].push_back(a) ; } for( i =1 ; i <= n ;i++) sort(qe[i].begin(),qe[i].end()); for( i = 1 ; i <= n ;i++) { len = qe[i].size(); if(len==0) continue ; u = 0 ; v=1; init(n*2); for( j = i ; j <= n ;j++) { add(str1[j]-‘a‘,v++); while(u < len && qe[i][u].R == j) { ans[qe[i][u].id] = find(); u++; } if(u==len) break ; } } for( i = 1 ; i <= m ;i++) printf("%d\n",ans[i]); } return 0 ;}
后缀自动机总结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。