[SDOI2016]生成魔咒 后缀自动机

这是一道模板题。

每新加入一个字符，所产生的子串种类贡献即为 $dis[np]-dis[f[np]]$，广义 SAM 也同理

Code:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map> 
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 300007 
using namespace std;
map<int,int>ch[maxn]; 
map<int,int>::iterator  it;
int f[maxn],dis[maxn],last,tot,n,A[maxn],arr[maxn]; 
long long ans; 
void init(){ last=tot=1; }
void ins(int c){
    int p=last,np=++tot; last=np,dis[np]=dis[p]+1;
    while(p&&!ch[p][c]) ch[p][c]=np,p=f[p];
    if(!p) f[np]=1;
    else {
        int q=ch[p][c];
        if(dis[q]==dis[p]+1) f[np]=q; 
        else{
            int nq=++tot;
            dis[nq]=dis[p]+1,ch[nq]=ch[q];
            f[nq]=f[q],f[np]=f[q]=nq; 
            while(p&&ch[p][c]==q) ch[p][c]=nq,p=f[p]; 
        }
    }
    ans+=dis[last]-dis[f[last]]; 
}  
int main(){
    //setIO("input");
    scanf("%d",&n),init(); 
    for(int i=1;i<=n;++i) scanf("%d",&arr[i]),A[i]=arr[i]; 
    sort(A+1,A+1+n);
    for(int i=1;i<=n;++i) arr[i]=lower_bound(A+1,A+1+n,arr[i])-A;
    for(int i=1;i<=n;++i) ins(arr[i]),printf("%lld
",ans); 
}