后缀自动机是通过一个DAG图来存储的,使空间更小,后缀自动机中最关键的一项技术叫做后缀链。
1.建立SAM
void insert(int c){ newNode(t[last].len+1); int p=last,cur=sz; while(p!=-1&&!t[p].son[c])t[p].son[c]=cur,p=t[p].father; if(p==-1)t[cur].father=0; else{ int q=t[p].son[c]; if(t[q].len==t[p].len+1)t[cur].father=q; else{ newNode(t[p].len+1); int nq=sz; memcpy(t[nq].son,t[q].son,sizeof(t[q].son)); t[nq].father=t[q].father; t[cur].father=t[q].father=nq; while(p>=0&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].father; } } last=cur; }
2.例题:HDU4622
这道题求的是区间内不同的子串个数,可以使用dp的思路,递推求解所有区间的答案
#include<bits/stdc++.h> using namespace std; const int N = 2e3+255; int sz,last,ans[N][N]; char s[N]; struct node{ int son[26],father,len; }t[N<<1]; void newNode(int length){ t[++sz].len=length; t[sz].father=-1; memset(t[sz].son,0,sizeof(t[sz].son)); } void init(){ sz=-1;last=0; newNode(0); } void insert(int c){ newNode(t[last].len+1); int p=last,cur=sz; while(p!=-1&&!t[p].son[c])t[p].son[c]=cur,p=t[p].father; if(p==-1)t[cur].father=0; else{ int q=t[p].son[c]; if(t[q].len==t[p].len+1)t[cur].father=q; else{ newNode(t[p].len+1); int nq=sz; memcpy(t[nq].son,t[q].son,sizeof(t[q].son)); t[nq].father=t[q].father; t[cur].father=t[q].father=nq; while(p>=0&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].father; } } last=cur; } int main(){ int T;cin>>T; while(T--){ cin>>s; int n=strlen(s); for(int i=0;i<n;i++){ init(); for(int j=i;j<n;j++){ insert(s[j]-'a'); ans[i][j]=ans[i][j-1]+t[last].len-t[t[last].father].len; } } int Q,l,r;cin>>Q; while(Q--){ cin>>l>>r; cout<<ans[--l][--r]<<'\n'; } } return 0; }
标签:cur,后缀,father,len,son,int,nq,自动机 From: https://www.cnblogs.com/zhanghx-blogs/p/17278387.html