[HAOI2016]找相同子串

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 const int N=400010; 6 char s[N];int len,d; 7 int r[N],Wa[N],Wb[N],sa[N],rk[N]; 8 int Ws[N],Wv[N],lcp[N]; 9 10 bool cmp(int *p,int i,int j,int l){11     return p[i]==p[j]&&p[i+l]==p[j+l];12 }13 14 void DA(int n,int m){15     int i,j,p,*x=Wa,*y=Wb;16     for(i=0;i<m;i++)Ws[i]=0;17     for(i=0;i<n;i++)++Ws[x[i]=r[i]];18     for(i=1;i<m;i++)Ws[i]+=Ws[i-1];19     for(i=n-1;i>=0;i--)sa[--Ws[x[i]]]=i;20     for(j=1,p=1;p<n;j<<=1,m=p){21         for(p=0,i=n-j;i<n;i++)y[p++]=i;22         for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;23         for(i=0;i<m;i++)Ws[i]=0;24         for(i=0;i<n;i++)++Ws[Wv[i]=x[y[i]]];25         for(i=1;i<m;i++)Ws[i]+=Ws[i-1];26         for(i=n-1;i>=0;i--)sa[--Ws[Wv[i]]]=y[i];27         for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++)28             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;29     }30 }31 32 void LCP(int n){33     int i,j,k=0;34     for(i=1;i<=n;i++)rk[sa[i]]=i;35     for(i=0;i<n;lcp[rk[i++]]=k)36         for(k?k--:k,j=sa[rk[i]-1];r[i+k]==r[j+k];k++);37 }38 39 int ID(int x){x=sa[x];40     if(x==d)return 0;41     if(x<d)return 1;42     return 2; 43 }44 45 int st[N]={-1},top;46 long long sum[N],tot[N],ans;47 int main(){48     freopen("find_2016.in","r",stdin);49     freopen("find_2016.out","w",stdout);50     scanf("%s",s);51     len=d=strlen(s);52     scanf("%s",s+len+1);53     s[d]=‘#‘;len=strlen(s);54     for(int i=0;i<len;i++)r[i]=s[i];55     DA(len+1,128);LCP(len);56     for(int i=1;i<=len;i++){57         if(!ID(i))continue;58         if(ID(i)==2)ans+=tot[top];59         if(i!=len){60             st[++top]=lcp[i+1];sum[top]=2-ID(i);61             tot[top]=st[top]*sum[top]+tot[top-1];62             while(st[top]<=st[top-1]){63                 sum[top-1]+=sum[top];64                 st[top-1]=st[top];top--;65                 tot[top]=st[top]*sum[top]+tot[top-1];66             }67         }68     }69     top=0;70     for(int i=1;i<=len;i++){71         if(!ID(i))continue;72         if(ID(i)==1)ans+=tot[top];73         if(i!=len){74             st[++top]=lcp[i+1];sum[top]=ID(i)-1;75             tot[top]=st[top]*sum[top]+tot[top-1];76             while(st[top]<=st[top-1]){77                 sum[top-1]+=sum[top];78                 st[top-1]=st[top];top--;79                 tot[top]=st[top]*sum[top]+tot[top-1];80             }81         }82     }83     printf("%lld\n",ans);84     return 0;85 }