广义后缀自动机--bzoj3926: [Zjoi2015]诸神眷顾的幻想乡

本文主要是介绍广义后缀自动机--bzoj3926: [Zjoi2015]诸神眷顾的幻想乡，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

因为叶子只有$20$个，所以把每个叶子当作根然后把从根开始的所有子串都插入一个广义后缀自动机，这样就可以把所有串取到，每次插入的时候记录一下$fa$是哪个，从那个开始插就好了

这个要求不同子串个数要用${\sum }_{i=1}^{cnt}len[i]-len[f{a}_i]$
因为$f{a}_i$是$i$的一个后缀，然后$len$记得是最长长度，所以减一下就是新增的不同子串个数

什么时候打$SAM$就不用看板子了啊

代码如下：

#include<bits/stdc++.h>
#define N 100005
#define M 2000005
#define LL long long
using namespace std;template<class T>inline void rd(T &x){x=0; short f=1; char c=getchar();while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();x*=f;
}int n,m,cnt,head[N],nxt[N<<1],to[N<<1],val[N],deg[N];inline void add(int x,int y){to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;to[++cnt]=x,nxt[cnt]=head[y],head[y]=cnt;
}struct SAM{int len[M],ch[M][10],fa[M],cnt;SAM(){cnt=1;}inline int insert(int c,int p){int np=++cnt; len[np]=len[p]+1;while(p&&!ch[p][c]) ch[p][c]=np,p=fa[p];if(!p) fa[np]=1;else{int q=ch[p][c];if(len[p]+1==len[q]) fa[np]=q;else{int nq=++cnt; len[nq]=len[p]+1;memcpy(ch[nq],ch[q],sizeof ch[q]);fa[nq]=fa[q],fa[q]=fa[np]=nq;while(ch[p][c]==q) ch[p][c]=nq,p=fa[p];}} return np;}inline LL solve(){LL ans=0;for(int i=1;i<=cnt;i++) ans+=len[i]-len[fa[i]];return ans;}
}sam;void dfs(int u,int fa,int p){int t=sam.insert(val[u],p);for(int i=head[u],v;i;i=nxt[i])if((v=to[i])!=fa) dfs(v,u,t);
}int main(){rd(n); rd(m); int x,y;for(int i=1;i<=n;i++) rd(val[i]);for(int i=1;i<n;i++){rd(x),rd(y);add(x,y); deg[x]++,deg[y]++;}for(int i=1;i<=n;i++)if(deg[i]==1) dfs(i,0,1);printf("%lld\n",sam.solve());return 0;
}

这篇关于广义后缀自动机--bzoj3926: [Zjoi2015]诸神眷顾的幻想乡的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---