BZOJ3238：[AHOI2013]差异—

BZOJ3238：[AHOI2013]差异——题解

阅读量：6956 次

发布时间：2019-06-27

本文共 1563 字，大约阅读时间需要 5 分钟。

参考：

第一道接触后缀树的题，然而不想讲这个东西。

我们只需要知道将串倒着建后缀自动机parent树就是后缀树即可。

然后两个后缀的lcp就是他们的lca的len。

设点u，则过点u的后缀就有su子树的size和个，所以能配出size[u]*(size[u]-1)/2个对，这条路径的长度贡献为(tr[u].l-tr[f].l)

PS：贡献不是tr[u].l，因为过u的后缀最长的不一定为tr[u].l，所以要一段一段处理。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;const int N=1e6+5;struct tree{ int a[26],fa,l;}tr[N];struct node{ int to,nxt;}e[N];char s[N];int last,cnt,tot,size[N],head[N];inline void add(int u,int v){ e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;}inline void insert(int c){ int p=last,np=++tot; last=np;tr[np].l=tr[p].l+1; for(;p&&!tr[p].a[c];p=tr[p].fa)tr[p].a[c]=np; if(!p)tr[np].fa=1; else{ int q=tr[p].a[c]; if(tr[p].l+1==tr[q].l)tr[np].fa=q; else{ int nq=++tot;tr[nq].l=tr[p].l+1; memcpy(tr[nq].a,tr[q].a,sizeof(tr[q].a)); tr[nq].fa=tr[q].fa;tr[q].fa=tr[np].fa=nq; for(;p&&tr[p].a[c]==q;p=tr[p].fa)tr[p].a[c]=nq; } } size[np]=1;}ll ans=0;void dfs(int u,int f){ for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; dfs(v,u); size[u]+=size[v]; } ans-=(ll)size[u]*(size[u]-1)*(tr[u].l-tr[f].l);}int main(){ cin>>s+1; int n=strlen(s+1); last=tot=1; for(int i=n;i>=1;i--)insert(s[i]-'a'); for(int i=2;i<=tot;i++)add(tr[i].fa,i); ans=(ll)(n-1)*n*(n+1)>>1; dfs(1,0); printf("%lld\n",ans); return 0;}