顯然只需求LCP(i,j)就可以了。 將s反轉,然後插入尾碼自動機。由於尾碼自動機的link指針構成了一棵尾碼樹,而字元串又反轉過,所以兩個結點的LCP就是LCA。 樹形DP,求出以每個結點為LCA的個數就可以了。 代碼: 1 #include<iostream> 2 #include<cstdio ...
顯然只需求LCP(i,j)就可以了。
將s反轉,然後插入尾碼自動機。由於尾碼自動機的link指針構成了一棵尾碼樹,而字元串又反轉過,所以兩個結點的LCP就是LCA。
樹形DP,求出以每個結點為LCA的個數就可以了。
代碼:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 #define N 500001 6 #define ll long long 7 ll f[N<<2],k,Ans; 8 int i,j,n,m,Link[N<<2],Len[N<<2],Last,Cur,Num,Next[N<<2][26],Sum[N<<2],g[N<<2],b[N],r[N<<2],x; 9 char s[N]; 10 inline void Insert(int x){ 11 Cur=++Num;Len[Cur]=Len[Last]+1;f[Cur]=g[Cur]=1; 12 int p; 13 for(p=Last;p&&!Next[p][x];p=Link[p])Next[p][x]=Cur; 14 if(!p)Link[Cur]=1;else{ 15 int q=Next[p][x]; 16 if(Len[p]+1==Len[q])Link[Cur]=q;else{ 17 int C=++Num;Len[C]=Len[p]+1; 18 Link[C]=Link[q];memcpy(Next[C],Next[q],sizeof(Next[q])); 19 for(;p&&Next[p][x]==q;p=Link[p])Next[p][x]=C; 20 Link[q]=Link[Cur]=C; 21 } 22 }Last=Cur; 23 } 24 int main() 25 { 26 scanf("%s",&s); 27 n=strlen(s);Last=Num=1; 28 for(i=n-1;i>=0;i--)Insert(s[i]-'a'); 29 for(i=1;i<=Num;i++)b[Len[i]]++; 30 for(i=1;i<=n;i++)b[i]+=b[i-1]; 31 for(i=1;i<=Num;i++)r[b[Len[i]]--]=i; 32 for(i=Num;i;i--)f[Link[r[i]]]+=f[r[i]]; 33 for(i=1;i<=Num;i++){ 34 x=r[i]; 35 Ans+=1ll*g[Link[x]]*f[x]*Len[Link[x]]; 36 g[Link[x]]+=f[x]; 37 } 38 printf("%lld",(1ll*n*(n-1)*(n+1)>>1)-(Ans<<1)); 39 return 0; 40 }bzoj3238