luogu P4248 [AHOI2013]差异 SAM

luogu P4248 [AHOI2013]差异

链接

luogu

思路

\(\sum\limits_{1<=i<j<=n}{{len}(T_i)+{len}(T_j)-2*{lcp}(T_i,T_j)}\)

=\(\sum\limits_{1<=i<j<=n}{{len}(T_i)+{len}(T_j)}-\sum\limits_{1<=i<j<=n}2*{lcp}(T_i,T_j)\)

前半部分是\(\frac{n*(n+1)(n-1)}{2}\)

后半部分用sam求出parent tree的siz的过程中求解就行了。

两个串的lcp就是他们的lca的longest。

考虑子树内的贡献就行了。

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N=1e6+7;

int n,c[N<<1],a[N<<1];

char s[N];

struct sam {

    int len,fa,ch[26];

}dian[N<<1];

int siz[N<<1],las=1,tot=1;

void add(int c,int k_th) {

    int p=las;int np=las=++tot;

    dian[np].len=dian[p].len+1;

    for(;p&&!dian[p].ch[c];p=dian[p].fa) dian[p].ch[c]=np;

    if(!p) dian[np].fa=1;

    else {

        int q=dian[p].ch[c];

        if(dian[q].len==dian[p].len+1) dian[np].fa=q;

        else {

            int nq=++tot;

            dian[nq]=dian[q];

            dian[nq].len=dian[p].len+1;

            dian[q].fa=dian[np].fa=nq;

            for(;p&&dian[p].ch[c]==q;p=dian[p].fa)

                dian[p].ch[c]=nq;

        }

    }

    siz[las]=1;

}

signed main() {

    scanf("%s",s+1);

    n=strlen(s+1);

    for(int i=n;i>=1;--i) add(s[i]-'a',i);

    for(int i=1;i<=tot;++i) c[dian[i].len]++;

    for(int i=1;i<=tot;++i) c[i]+=c[i-1];

    for(int i=1;i<=tot;++i) a[c[dian[i].len]--]=i;

    int ans=1LL*n*(n+1)*(n-1)/2;

    for(int i=tot;i>=1;--i) {

        ans-=2LL*siz[a[i]]*siz[dian[a[i]].fa]*dian[dian[a[i]].fa].len;

        siz[dian[a[i]].fa]+=siz[a[i]];

    }

    printf("%lld",ans);

    return 0;

}