给出一个长度为\(n\)的字符串\(s\)，令\(T_i\)表示\(s\)从\(i\)开始的后缀，求：\[ \begin{aligned} \sum _{i=1}^{n-1}\sum _{j=i+1}^{n}len(T_i)+len(T_j)-2lcp(T_i,T_j) \end{aligned} \]
简单题，后缀自动机建出后缀树dfs一次即可。注意要求什么！！！
虽然后缀自动机是\(O(n)\)的，但是由于会新建点，所以空间要开两倍！！！！
#include<cstdio> #include<cctype> #include<cstring> #include<algorithm> using namespace std; typedef long long giant; int read() { int x=0,f=1; char c=getchar(); for (;!isdigit(c);c=getchar()) if (c=='-') f=-1; for (;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=1e6+1; const int maxc=26; char s[maxn]; int a[maxn]; bool spe[maxn]; struct edge { int v,w,nxt; } e[maxn]; int h[maxn],tot=0; void add(int u,int v,int w) { e[++tot]=(edge){v,w,h[u]}; h[u]=tot; } struct SAM { int t[maxn][maxc],link[maxn],len[maxn],tot,last; SAM ():tot(1),last(1) {} void insert(int c) { int nw=++tot,i; spe[nw]=true; len[nw]=len[last]+1; for (i=last;i && !t[i][c];i=link[i]) t[i][c]=nw; if (i) { int p=t[i][c]; if (len[p]==len[i]+1) link[nw]=p; else { int q=++tot; for (int j=i;j && t[j][c]==p;j=link[j]) t[j][c]=q; memmove(t[q],t[p],sizeof t[p]); link[q]=link[p]; link[p]=link[nw]=q; len[q]=len[i]+1; } } else link[nw]=1; last=nw; } void run() { for (int i=2;i<=tot;++i) add(link[i],i,len[i]-len[link[i]]); } } sam; int size[maxn],dep[maxn]; giant ans; void dfs(int x,int fa) { size[x]=spe[x]; for (int i=h[x],v=e[i].v,w=e[i].w;i;i=e[i].nxt,v=e[i].v,w=e[i].w) if (v!=fa) { dep[v]=dep[x]+w; dfs(v,x); ans-=2ll*size[x]*size[v]*dep[x]; size[x]+=size[v]; } } int main() { #ifndef ONLINE_JUDGE freopen("test.in","r",stdin); #endif scanf("%s",s+1); int n=strlen(s+1); for (int i=n;i;--i) sam.insert(s[i]-'a'); sam.run(); ans=(giant)(n-1)*n*(n+1)/2; dfs(1,0); printf("%lld\n",ans); return 0; }转载于:https://www.cnblogs.com/owenyu/p/6724618.html
