2019/5/22 day7 解题日志

2019-05-22

字数统计: 630字 | 阅读时长: 3分

给定一个长度为 $n$ 的字符串 $S$，令 $T_i$ 表示它从第 $i$ 个字符开始的后缀。求$\sum_{1 \le i \lt j \le n} \text{len}(T_i)+\text{len}(T_j)-2 \times \text{lcp}(T_i,T_j)$。
其中，$len(a)$ 表示字符串 $a$ 的长度，$lcp(a,b)$ 表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。

day7

后缀数组 + 单调栈

思路

不妨把式子拆开来看，首先可以直接算出$\sum_{1 \le i \lt j \le n} \text{len}(T_i)+\text{len}(T_j)$。
显然这个值等于$len(S)(len(S)+1)(len(S)-1)/2$。
那么如何算$\sum_{1 \le i \lt j \le n}\text{lcp}(T_i,T_j)$呢？

只需要算出对于每个后缀$suf_i$，$\sum_{j\lt i} lcp(suf_i,suf_j)$，这个需要用到后缀数组预处理，然后根据height数组的性质，用单调栈维护便可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
int len;
pair<int,ll> stk[maxn];
struct SA{
    int rk[maxn],sa[maxn],height[maxn];
    int t1[maxn],t2[maxn],c[maxn];
    bool cmp(int *s,int a,int b,int l){
        return s[a]==s[b]&&s[a+l]==s[b+l];
    }
    void Sa(char *s,int n,int m){
        n++;
        int i,j,p,*x=t1,*y=t2;
        for(i=0;i<m;i++)c[i]=0;
        for(i=0;i<n;i++)c[x[i]=s[i]]++;
        for(i=1;i<m;i++)c[i]+=c[i-1];
        for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
        for(j=1;j<=n;j<<=1){
            p=0;
            for(i=n-j;i<n;i++)y[p++]=i;
            for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
            for(i=0;i<m;i++)c[i]=0;
            for(i=0;i<n;i++)c[x[y[i]]]++;
            for(i=1;i<m;i++)c[i]+=c[i-1];
            for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
            swap(x,y);
            p=1;x[sa[0]]=0;
            for(i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
            if(p>=n)break;m=p;
        }
        int k=0;n--;
        for(i=0;i<=n;i++)rk[sa[i]]=i;
        for(i=0;i<n;i++){
            if(k)k--;
            j=sa[rk[i]-1];
            while(s[i+k]==s[j+k])k++;
            height[rk[i]]=k;
        }
    }
    void solve(int n){
        ll ans=0;
        int top=0;
        stk[0]=make_pair(1,0);
        for(int i=1;i<=n;i++){
            while(top &&height[stk[top].first]>height[i])top--;++top;
            stk[top]=make_pair(i,stk[top-1].second+(i-stk[top-1].first)*height[i]);
            ans+=stk[top].second;
        }cout<<1ll*(n-1)*(1+n)*n/2-2*ans<<endl;
    }
}sa;

char s[maxn];
int main(){
    scanf("%s",s);
    len=strlen(s);
    sa.Sa(s,len,128);
    sa.solve(len);
    return 0;
}

后缀自动机

留坑。