字符串（后缀自动机）：Ahoi2013 差异

Description

Input

一行，一个字符串S

Output

一行，一个整数，表示所求值

Sample Input

cacao

Sample Output

HINT

2<=N<=500000,S由小写英文字母组成

　　建反向前缀树，O（N）dp求解。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 const int N=1000010;
 6 int fa[N],ch[N][26],len[N],cnt,lst;
 7 int cntE,fir[N],to[N],nxt[N],dp[N];
 8 char s[N];
 9 void Init(){lst=cnt=1;}
10 void Insert(int c){
11     int p=lst,np=lst=++cnt;len[np]=len[p]+1;
12     while(p&&ch[p][c]==0)ch[p][c]=np,p=fa[p];
13     if(!p)fa[np]=1;
14     else{
15         int q=ch[p][c],nq;
16         if(len[p]+1==len[q])
17             fa[np]=q;
18         else{
19             len[nq=++cnt]=len[p]+1;
20             fa[nq]=fa[q];fa[q]=fa[np]=nq;
21             memcpy(ch[nq],ch[q],sizeof(ch[q]));
22             while(ch[p][c]==q)ch[p][c]=nq,p=fa[p];
23         }    
24     }
25 }
26 
27 void addedge(int a,int b){
28     nxt[++cntE]=fir[a];
29     to[fir[a]=cntE]=b;
30 }
31 int end[N];
32 long long ans; 
33 void DFS(int x){
34     int sum=0;
35     for(int i=fir[x];i;i=nxt[i]){
36         DFS(to[i]);
37         ans-=2ll*len[x]*dp[to[i]]*dp[x];
38         dp[x]+=dp[to[i]];
39     }        
40 }
41 
42 int main(){
43     Init();
44     scanf("%s",s+1);
45     int l=strlen(s+1);
46     ans=1LL*(l-1)*(l+1)*l/2;
47     for(int i=l;i>=1;i--)
48         Insert(s[i]-'a'),dp[lst]+=1;
49     
50     for(int i=2;i<=cnt;i++)
51         addedge(fa[i],i);
52     DFS(1);    
53     printf("%lld
",ans);
54     return 0;
55 }