bzoj 3238 差異

給出一個長n的字元集為小寫字母的字元串，求 ∑1≤i<j≤nlen(Suffixi)+len(Suffixj)−2×len(lcp(Suffixi,Suffixj))

Suffixx 代表從 x 開始的字尾，lcp(stra,strb)表示 stra , strb 的最長公共字首, len(str) 表示 str 的長度

如果我們擁有這個字元串的字尾樹，将每個字尾所對應的節點記為标記點。

對每一個标記點對，我們統計的其實是這兩個點到根的距離和減去根到他們 LCA 的距離的二倍。也就是這兩個點之間的路徑的距離。

那我們要求的實際上就是樹上所有标記點對的距離和。

以下不加證明的給出一個結論

一個字元串翻轉的字尾自動機的 parent 樹就是在這個字元串的字尾樹上将字尾對應的節點作為關鍵點所建立的虛樹， parent 樹中子節點和父節點的 len 的內插補點就是這兩個點在字尾樹上的距離。

有了上面那個結論之後我們就可以用 SAM 建立字尾樹，在字尾樹上做一下樹dp就可以了。

#include<bits/stdc++.h>
using namespace std;

const int maxn = ,mlen = ;
#define LL long long 

LL ans;
LL dp[maxn*],siz[maxn*];
vector<pair<int,int> >edge[maxn*];
void Link(int st,int ed,int v){
    edge[st].push_back(make_pair(ed,v));
    edge[ed].push_back(make_pair(st,v));
}

struct Sam{
    int len[maxn*],fa[maxn*],nex[maxn*][mlen];
    int val[maxn*];
    int _cnt,root,omg;
    int newNode(int L = ){
        len[_cnt] = L;
        memset(nex[_cnt],fa[_cnt] = -,sizeof(nex[_cnt]));
        return _cnt++;
    }
    void init(){
        _cnt = ;
        memset(val,,sizeof(val));
        root = omg = newNode();
    }
    void extend(int x){
        int ox = newNode(len[omg]+);
        val[ox]++;
        while(omg != - && nex[omg][x] == -){
            nex[omg][x] = ox;
            omg = fa[omg];
        }
        if(omg == -) fa[ox] = root;
        else{
            int omgx = nex[omg][x];
            if(len[omgx] == len[omg]+) fa[ox] = omgx;
            else{
                int mgx = newNode(len[omg]+);
                for(int i=;i<mlen;i++)
                    nex[mgx][i] = nex[omgx][i];
                fa[mgx] = fa[omgx];
                fa[omgx] = fa[ox] = mgx;
                while(omg != - && nex[omg][x] == omgx)
                    nex[omg][x] = mgx,omg = fa[omg];
            }
        }
        omg = ox;
    }
    void build(char *arr){
        init();
        for(int i=;arr[i];i++){
            extend(arr[i] - 'a');
        }
    }
    void treeBuild(){
        for(int i=;i<_cnt;i++){
            edge[i].clear();
            dp[i] =  , siz[i] = val[i];
        }
        for(int i=;i<_cnt;i++){
            if(fa[i] != -){
                Link(i,fa[i],len[i] - len[fa[i]]);
            }
        }
    }
}SAM;

char arr[maxn];

void dfs(int st,int fa = -){
    for(vector<pair<int,int> >::iterator it = edge[st].begin();
        it != edge[st].end();it++){
        pair<int,int> x = *it;
        if(x.first == fa) continue;
        dfs(x.first,st);
        ans += dp[st] * siz[x.first] + (dp[x.first] + siz[x.first] * x.second) * siz[st];
        dp[st] += dp[x.first] + siz[x.first] * x.second; 
        siz[st] += siz[x.first];
    }
}

int main(){
    scanf("%s",arr);
    int len = strlen(arr);
    reverse(arr,arr+len);
    SAM.build(arr);
    SAM.treeBuild();
    ans = ;
    dfs(SAM.root);
    printf("%lld\n",ans);
    return ;
}