[BZOJ3926] [Zjoi20150]诸神眷顾的幻想乡

本文主要是介绍[BZOJ3926] [Zjoi20150]诸神眷顾的幻想乡，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=3926

题目大意

求本质不同子串个数

题解

广义SAM

typedata=recordlen,fa:longint;tranc:array[0..9]of longint;end; //48
varx:array[0..10000000]of data;z,deg:array[0..100005]of longint; //1.2w:array[0..3*100005,1..2]of longint; //2.4i,j,k:longint;n,m,tot,len,a,b:longint;ans:int64;
procedure init(a,b:longint);
beginw[len,1]:=b; if w[a,2]=0 then w[a,2]:=len else w[w[a,1],2]:=len;w[a,1]:=len; inc(len);
end;function insert(a,tail:longint):longint;
var p,np,q,nq:longint;
begininc(tot); np:=tot; x[np].len:=x[tail].len+1;p:=tail;while (p<>0)and(x[p].tranc[a]=0) dobeginx[p].tranc[a]:=np;p:=x[p].fa;end;if x[p].tranc[a]=0then x[p].tranc[a]:=npelsebeginq:=x[p].tranc[a];if x[q].len=x[p].len+1then x[np].fa:=qelsebegininc(tot); nq:=tot; x[nq]:=x[q];x[q].fa:=nq; x[np].fa:=nq;x[nq].len:=x[p].len+1;while x[p].tranc[a]=q dobeginx[p].tranc[a]:=nq;p:=x[p].fa;end;end;end;inc(ans,x[np].len-x[x[np].fa].len);exit(np);   
end;procedure dfs(a,fa,b:longint);
var tt,t1:longint;
begintt:=w[a,2]; t1:=insert(z[a],b);while tt<>0 dobeginif w[tt,1]<>fathen dfs(w[tt,1],a,t1);tt:=w[tt,2];end;
end;beginreadln(n,m); len:=n+1; ans:=0;for i:=1 to n doread(z[i]);for i:=1 to n-1 dobeginreadln(a,b);init(a,b); init(b,a);inc(deg[a]); inc(deg[b]);end;for i:=1 to n doif deg[i]=1then dfs(i,0,0);writeln(ans);
end.

这篇关于[BZOJ3926] [Zjoi20150]诸神眷顾的幻想乡的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---