地址：

题目：

3238: [Ahoi2013]差异

Time Limit: 20 Sec  Memory Limit: 512 MB

Submit: 3367  Solved: 1532

[][][]

Description

Input

一行，一个字符串S

Output

 

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

Sample Input

cacao

Sample Output

54

HINT

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

 

思路：

　　很明显前面的len[i]+len[j]是不变的，所以可以直接求出，对于后面的有俩种做法：

　　后缀自动机做法：

　　　我们知道沿parent树往上走是不断取后缀，也就是不断删首字母。

　　　所以如果把字符串反转，然后沿parent树往上走则是对前缀不断取前缀的过程，也就是不断删尾字母。

　　　这时parent树就成lcp树，树上每个状态都是一些子串的lcp，所以树dp一下即可。

　　　这个树dp部分有点巧妙，学习别人的，要我写会写成dfs的形式。

sam做法：

1 /************************************************************** 2     Problem: 3238 3     User: weeping 4     Language: C++ 5     Result: Accepted 6     Time:3356 ms 7     Memory:122876 kb 8 ****************************************************************/ 9  10 #include 
      
       11  12 using namespace std;13  14 struct SAM15 {16     static const int MAXN = 500002<<1;//大小为字符串长度两倍17     static const int LetterSize = 26;18  19     int tot, last, ch[MAXN][LetterSize], fa[MAXN], len[MAXN];20     int sum[MAXN], tp[MAXN], cnt[MAXN]; //sum,tp用于拓扑排序，tp为排序后的数组21  22     void init( void)23     {24         last = tot = 1;25         len[1] = 0;26         memset(ch,0,sizeof ch);27         memset(fa,0,sizeof fa);28         memset(cnt,0,sizeof cnt);29     }30  31     void add( int x)32     {33         int p = last, np = last = ++tot;34         len[np] = len[p] + 1, cnt[last] = 1;35         while( p && !ch[p][x]) ch[p][x] = np, p = fa[p];36         if( p == 0)37             fa[np] = 1;38         else39         {40             int q = ch[p][x];41             if( len[q] == len[p] + 1)42                 fa[np] = q;43             else44             {45                 int nq = ++tot;46                 memcpy( ch[nq], ch[q], sizeof ch[q]);47                 len[nq] = len[p] + 1, fa[nq] = fa[q], fa[q] = fa[np] = nq;48                 while( p && ch[p][x] == q)  ch[p][x] = nq, p = fa[p];49             }50         }51     }52  53     void toposort( void)54     {55         for(int i = 1; i <= len[last]; i++)   sum[i] = 0;56         for(int i = 1; i <= tot; i++)   sum[len[i]]++;57         for(int i = 1; i <= len[last]; i++)   sum[i] += sum[i-1];58         for(int i = 1; i <= tot; i++)   tp[sum[len[i]]--] = i;59     }60  61     void work(void)62     {63         toposort();64         long long ans=1LL*len[last]*(len[last]+1)*(len[last]-1)/2;65         for(int i=tot;i;i--)66             ans-=2LL*cnt[fa[tp[i]]]*len[fa[tp[i]]]*cnt[tp[i]],cnt[fa[tp[i]]]+=cnt[tp[i]];67         printf("%lld\n",ans);68     }69 } sam;70  71 char sa[500005];72  73 int main( void)74 {75     scanf("%s",sa);76     sam.init();77     for(int i=strlen(sa)-1;i>-1;i--)   sam.add(sa[i]-'a');78     sam.work();79     return 0;80 }