BZOJ.3926.[ZJOI2015]诸神眷顾的幻想乡(广义后缀自动机)

题目链接

要对多个串同时建立SAM&＃xff0c;有两种方法&＃xff1a;
1.将所有串拼起来&＃xff0c;中间用分隔符隔开&＃xff0c;插入字符正常插入即可。
2.在这些串的Trie上建SAM。实际上并不需要建Trie&＃xff0c;还是只需要正常插入&＃xff08;因为本来就差不多&＃xff1f;&＃xff09;。在要插入下一个串时需把las重新设为root。这就是广义后缀自动机。

对于本题&＃xff0c;因为叶节点最多只有20个&＃xff08;别理解错了啊喂&＃xff09;&＃xff0c;以这些叶节点分别为根&＃xff0c;DFS整棵树建Trie&＃xff08;当然原图就是&＃xff09;&＃xff0c;这样所有子串就在Trie上某条路径中。这样就成了求不同子串的个数。
当然还是不需要建Trie&＃xff0c;依次插入SAM即可。如果当前有要插入点的转移&＃xff0c;则不再新建np&＃xff0c;而是直接用p(las)做np。否则会有很多重复节点&＃xff08;虽然不影响正确性吧&＃xff09;。
每次插入一个字符&＃xff0c;其产生的子串一共有len[i]个&＃xff08;就是以它为右端点的后缀&＃xff09;&＃xff0c;不同的子串则有len[i]-len[fa[i]]个。所有节点的贡献求和即为答案。

注意会有20次建SAM&＃xff0c;空间要够&＃xff01;还有longlong。

//221660kb 2580ms
#include
#include
#include
#include
//#define gc() getchar()
#define MAXIN 1000000
#define gc() (SS&＃61;&＃61;TT&&(TT&＃61;(SS&＃61;IN)&＃43;fread(IN,1,MAXIN,stdin),SS&＃61;&＃61;TT)?EOF:*SS&＃43;&＃43;)
const int N&＃61;1e5&＃43;7,S&＃61;N*20*2;int n,C,A[N],dgr[N],Enum,H[N],nxt[N<<1],to[N<<1];
char IN[MAXIN],*SS&＃61;IN,*TT&＃61;IN;
struct Suffix_Automaton
{int tot,las,fa[S],son[S][11],len[S];void Init(){tot&＃61;las&＃61;1;}int Insert(int p,int c){int las;if(son[p][c]){int q&＃61;son[p][c];if(len[q]&＃61;&＃61;len[p]&＃43;1) las&＃61;q;else{int nq&＃61;&＃43;&＃43;tot; len[las&＃61;nq]&＃61;len[p]&＃43;1;memcpy(son[nq],son[q],sizeof son[q]);fa[nq]&＃61;fa[q], fa[q]&＃61;nq;//不要想当然写fa[p]&＃61;nq q就代表np了 for(; son[p][c]&＃61;&＃61;q; p&＃61;fa[p]) son[p][c]&＃61;nq;}}else{int np&＃61;&＃43;&＃43;tot; len[las&＃61;np]&＃61;len[p]&＃43;1;for(; p&&!son[p][c]; p&＃61;fa[p]) son[p][c]&＃61;np;if(!p) fa[np]&＃61;1;else{int q&＃61;son[p][c];if(len[q]&＃61;&＃61;len[p]&＃43;1) fa[np]&＃61;q;else{int nq&＃61;&＃43;&＃43;tot; len[nq]&＃61;len[p]&＃43;1;memcpy(son[nq],son[q],sizeof son[q]);fa[nq]&＃61;fa[q], fa[np]&＃61;fa[q]&＃61;nq;for(; son[p][c]&＃61;&＃61;q; p&＃61;fa[p]) son[p][c]&＃61;nq;}}}return las;}void Calc(){long long ans&＃61;0;for(int i&＃61;2; i<&＃61;tot; &＃43;&＃43;i) ans&＃43;&＃61;(long long)(len[i]-len[fa[i]]);printf("%lld\n",ans);}
}sam;inline int read()
{int now&＃61;0;register char c&＃61;gc();for(;!isdigit(c);c&＃61;gc());for(;isdigit(c);now&＃61;now*10&＃43;c-&＃39;0&＃39;,c&＃61;gc());return now;
}
inline void AddEdge(int u,int v)
{&＃43;&＃43;dgr[v], to[&＃43;&＃43;Enum]&＃61;v, nxt[Enum]&＃61;H[u], H[u]&＃61;Enum;&＃43;&＃43;dgr[u], to[&＃43;&＃43;Enum]&＃61;u, nxt[Enum]&＃61;H[v], H[v]&＃61;Enum;
}
void DFS(int x,int f,int rt)
{int t&＃61;sam.Insert(rt,A[x]);for(int i&＃61;H[x]; i; i&＃61;nxt[i])if(to[i]!&＃61;f) DFS(to[i],x,t);
}int main()
{n&＃61;read(), C&＃61;read(), sam.Init();for(int i&＃61;1; i<&＃61;n; &＃43;&＃43;i) A[i]&＃61;read();for(int i&＃61;1; i}