Description
Input
一行，一个字符串S
Output
一行。一个整数。表示所求值
Sample Input
cacao
Sample Output54
HINT
2<=N<=500000,S由小写英文字母组成
后缀自己主动机的性质:
5.两个串的最长公共后缀,位于这两个串相应状态在Parent树上的近期公共祖先状态.
那么我们把原题里后缀的最长公共前缀反过来,把原串反过来建SAM就变成了最长公共后缀
然后题意就是求一个串全部前缀的最长公共后缀长度之和 我们能够在parent树上进行树形DP(按Po姐的说法事实上就是在后缀树上DP?)统计每一个点是多少点的LCA 对一个点统计子树两两right集合大小之积的和乘以深度 (别忘了是让你减掉这个东西)#include#include #include #include #include #define MAXN 1000100using namespace std;char ch[MAXN];int top;long long ans;struct edge{ int to; edge *next;}e[MAXN],*prev[MAXN];void insert(int u,int v){ e[++top].to=v;e[top].next=prev[u];prev[u]=&e[top];}struct sam{ int last,cnt,p,q,np,nq; int len[MAXN],fa[MAXN],a[MAXN][26],size[MAXN]; sam() { last=++cnt; } void insert(int c) { p=last;np=last=++cnt;len[np]=len[p]+1;size[np]=1; while (!a[p][c]&&p) a[p][c]=np,p=fa[p]; if (!p) fa[np]=1; else { q=a[p][c]; if (len[q]==len[p]+1) fa[np]=q; else { nq=++cnt;len[nq]=len[p]+1; memcpy(a[nq],a[q],sizeof(a[q])); fa[nq]=fa[q]; fa[q]=fa[np]=nq; while (a[p][c]==q) a[p][c]=nq,p=fa[p]; } } }}sam;void dfs(int x,int f){ for (edge *i=prev[x];i;i=i->next) { dfs(i->to,x); sam.size[x]+=sam.size[i->to]; } if (x==1) return; sam.len[x]-=sam.len[f]; ans-=(long long)sam.size[x]*(sam.size[x]-1)*sam.len[x];}int main(){ scanf("%s",ch);int Len=strlen(ch); for (int i=Len-1;i>=0;i--) sam.insert(ch[i]-'a'); ans=(long long)(Len-1)*Len*(Len+1)>>1; for (int i=2;i<=sam.cnt;i++) insert(sam.fa[i],i); dfs(1,0); cout< <