2022 牛客 多校 D Mi Re Do Si La? So Fa!

后缀数组

---

题意

给定长为 $n$ 的小写字符串 $s$ ，求所有子串的循环节的长度和。
其中 $1 \leq n \leq 10^6$ 。

思路

题意可以转换为找形如 $XX...X$ 的子串的个数，子串的贡献为循环节 $X$ 的长度。
考虑枚举 $X$ 的长度 $len$ ，对于循环节即为它本身的子串，我们直接加上贡献，对于循环节出现次数大于等于 $2$ 的子串，考虑用类似P1117 [NOI2016] 优秀的拆分的套路，在原串上每距离 $len$ 处设立一个标记点，第 $i$ 个记为 $p_i$ ，若一个子串包含了 $k (k \geq 2)$ 个循环节，则它一定经过恰好 $k$ 个标记点 $p_l, p_{l+1}, ..., p_r$ 。考虑枚举 $p_l$ ，统计左端点在区间 $[p_l - len + 1]$ 内的子串的贡献。具体的，求出原串以 $p_l$ 与 $p_{l+1}$ 为起点 / 终点的 $lcp$ 与 $lcs$ ，合法的起点个数即为 $min(lcs, len)$ ，对于 $k \geq 3$ 的情况即为 $lcp > len$ 的部分，这一部分子串的数量即为 $\lfloor \frac{lcp}{len} \rfloor$ ，对于 $k = 2$ 的情况，将 $lcp$ 与 $len$ 取模后直接计算 $lcp$ 与 $lcs$ 的重合部分即可。
总复杂度 $O(n \cdot logn)$ 。

代码

/*
    Author: Cupids_Bow
    Time: 2022-08-20 19:44:13
*/
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

constexpr int N=2e6+5;
int _=1;

int n;
ll ans;
struct SA{
    int n,m;
    char s[N];
    int sa[N],rk[N],height[N],h[N];
    int minn[21][N],lg[N];
    void init(int _n,int _m){
        n=_n;
        m=_m;
    }
    void buildsa(){
        static int oldrk[N<<1],id[N],px[N],cnt[N];
        int i,p,w;
        for(i=1;i<=m+1;i++) cnt[i]=0;
        for(i=1;i<=n+1;++i) sa[i]=rk[i]=id[i]=px[i]=0;
        for(i=1;i<=n*2;i++) oldrk[i]=0;
        for(i=1;i<=n;++i) ++cnt[rk[i]=(s[i]-'a'+1)];
        for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for(i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;
        for(w=1;;w<<=1,m=p){
            for(p=0,i=n;i>n-w;--i) id[++p]=i;
            for(i=1;i<=n;++i)
            if(sa[i]>w) id[++p]=sa[i]-w;
            for(i=1;i<=m;i++) cnt[i]=0;
            for(i=1;i<=n;++i) ++cnt[px[i]=rk[id[i]]];
            for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
            for(i=n;i>=1;--i) sa[cnt[px[i]]--]=id[i];
            for(i=1;i<=n;i++) oldrk[i]=rk[i];
            for(p=0,i=1;i<=n;++i)
            rk[sa[i]]=(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])?p:++p;
            if(p==n){
                for(i=1;i<=n;++i) sa[rk[i]]=i;
                break;
            }
        }
    }
    void buildheight(){
        for(int i=1;i<=n+1;++i) height[i]=h[i]=0;
        int k=0;
        for(int i=1;i<=n;i++){
            if(rk[i]==1) continue;
            if(k) --k;
            int j=sa[rk[i]-1];
            while(j+k<=n&&i+k<=n&&s[i+k]==s[j+k]) k++;
            height[rk[i]]=k;
        }
        for(int i=1;i<=n;i++) h[i]=height[rk[i]];
        for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
        for(int i=1;i<=n;i++) minn[0][i]=height[i];
        for(int j=1;(1<<j)<=n;j++)
            for(int i=1;i+(1<<j)-1<=n;i++) minn[j][i]=min(minn[j-1][i],minn[j-1][i+(1<<(j-1))]);
    }
    int get_lcp(int l,int r){
        if(l==r) return n-l+1;
        l=rk[l],r=rk[r];
        if(l>r) swap(l,r);
        l++;
        int k=lg[r-l+1];
        return min(minn[k][l],minn[k][r-(1<<k)+1]);
    }
}sa;

int get_lcp(int x,int y){
    if(x<1||x>n||y<1||y>n) return 0;
    return sa.get_lcp(x,y);
}

int get_lcs(int x,int y){
    if(x<1||x>n||y<1||y>n) return 0;
    x=n-x+1+n+1;
    y=n-y+1+n+1;
    return sa.get_lcp(x,y);
}

ll calc(int len){
    ll res=1ll*len*(n-len+1);
    for(int i=len;i+len<=n;i+=len){
        int x=min(get_lcs(i,i+len),len);
        int y=get_lcp(i+1,i+1+len);
        ll cnt=1ll*x*(y/len);
        y%=len;
        cnt+=max(0,y-(len-x)+1);
        res+=cnt*len;
    }
    return res;
}

void work(){
    ans=0;
    cin>>sa.s+1;
    n=strlen(sa.s+1);
    sa.s[n+1]=('z'+1);
    for(int i=1;i<=n;i++) sa.s[i+n+1]=sa.s[n-i+1];
    sa.init(n*2+1,27);
    sa.buildsa();
    sa.buildheight();
    for(int i=1;i<=n;i++) ans+=calc(i);
    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>_;
    while(_--){
        work();
    }

    return true&&false;
}