bzoj3238--后缀自动机

显然只需求LCP(i,j)就可以了。

将s反转，然后插入后缀自动机。由于后缀自动机的link指针构成了一棵后缀树，而字符串又反转过，所以两个结点的LCP就是LCA。

树形DP，求出以每个结点为LCA的个数就可以了。

代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define N 500001

 #define ll long long

 ll f[N<<],k,Ans;

 int i,j,n,m,Link[N<<],Len[N<<],Last,Cur,Num,Next[N<<][],Sum[N<<],g[N<<],b[N],r[N<<],x;

 char s[N];

 inline void Insert(int x){

   Cur=++Num;Len[Cur]=Len[Last]+;f[Cur]=g[Cur]=;

   int p;

   for(p=Last;p&&!Next[p][x];p=Link[p])Next[p][x]=Cur;

   if(!p)Link[Cur]=;else{

     int q=Next[p][x];

     if(Len[p]+==Len[q])Link[Cur]=q;else{

       int C=++Num;Len[C]=Len[p]+;

       Link[C]=Link[q];memcpy(Next[C],Next[q],sizeof(Next[q]));

       for(;p&&Next[p][x]==q;p=Link[p])Next[p][x]=C;

       Link[q]=Link[Cur]=C;

     }

   }Last=Cur;

 }

 int main()

 {

   scanf("%s",&s);

   n=strlen(s);Last=Num=;

   for(i=n-;i>=;i--)Insert(s[i]-'a');

   for(i=;i<=Num;i++)b[Len[i]]++;

   for(i=;i<=n;i++)b[i]+=b[i-];

   for(i=;i<=Num;i++)r[b[Len[i]]--]=i;

   for(i=Num;i;i--)f[Link[r[i]]]+=f[r[i]];

   for(i=;i<=Num;i++){

     x=r[i];

     Ans+=1ll*g[Link[x]]*f[x]*Len[Link[x]];

     g[Link[x]]+=f[x];

   }

   printf("%lld",(1ll*n*(n-)*(n+)>>)-(Ans<<));

   return ;

 }

bzoj3238