题目概述

LOJ2083

解题报告

想了很久匹配做法，不会做，实际上是性质题……

如果能求出 $pre_i$ 表示以 $i$ 结尾的 $AA$ 个数和 $suf_i$ 表示以 $i$ 开头的 $BB$ 个数，答案就是 $\sum_{i=1}^{n-1}pre_isuf_{i+1}$ 。

假设 $AA$ 的 $A$ 长度为 $i$ ，则 $AA$ 一定恰好跨越了 $j=ti,k=(t+1)i$ 两个点。因此我们可以考虑枚举 $i$ 以及 $j=ti,k=(t+1)i$ ，然后考虑经过 $j$ 和 $k$ 的所有 $AA$ 串。

假设 $j$ 和 $k$ 后缀的最长公共前缀为 $lcp+1$ ，$j$ 和 $k$ 前缀的最长公共后缀为 $lcs+1$ ，如果 $lcp+lcs\ge i-1$ ，就说明存在 $AA$ 串。假设 $A$ 串由 $j$ 的前 $x$ 个和 $k$ 的后 $y$ 个构成，则：

$$ x+y=i-1\\ 0\le x\le lcs,0\le y\le lcp\\ \max\{0,i-1-lcp\}\le x\le\min\{i-1,lcs\}\\ \max\{0,i-1-lcs\}\le y\le\min\{i-1,lcp\} $$

这样就可以得出 $pre$ 的贡献区间和 $suf$ 的贡献区间，用差分就可以快速求出 $pre$ 和 $suf$ 。

复杂度 $O(T(n\log_2n+n\ln n))$ 。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=30000,LOG=14;

int te,n;char s[maxn+5],t[maxn+5];
int SA[2][maxn+5],rk[2][maxn+5],ha[maxn+5],sc[(maxn<<1)+5];
int lg[maxn+5],RMQ[2][LOG+1][maxn+5];
int pre[maxn+5],suf[maxn+5];

void Sort(int id,int n,int m){
    for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[id][i]]++;
    for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[id][ha[rk[id][sc[i]]]--]=sc[i];
}
void MakeSA(int id,char *s,int n,int m=26){
    for (int i=1;i<=n;i++) rk[id][i]=s[i]-'a'+1,sc[i]=i,sc[i+n]=0;Sort(id,n,m);
    for (int k=1,p=0;p<n;m=p,k<<=1){
        p=0;for (int i=n-k+1;i<=n;i++) sc[++p]=i;
        for (int i=1;i<=n;i++) if (SA[id][i]>k) sc[++p]=SA[id][i]-k;
        Sort(id,n,m);for (int i=1;i<=n;i++) sc[i]=rk[id][i];rk[id][SA[id][1]]=p=1;
        for (int i=2;i<=n;i++)
            rk[id][SA[id][i]]=(p+=sc[SA[id][i-1]]!=sc[SA[id][i]] || sc[SA[id][i-1]+k]!=sc[SA[id][i]+k]);
    }
    for (int i=1,k=0;i<=n;i++){
        if (rk[id][i]==1) continue;if (k) k--;
        while (s[i+k]==s[SA[id][rk[id][i]-1]+k]) k++;
        RMQ[id][0][rk[id][i]]=k;
    }
    for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for (int j=1;(1<<j)<n;j++)
        for (int i=2;i+(1<<j)-1<=n;i++)
            RMQ[id][j][i]=min(RMQ[id][j-1][i],RMQ[id][j-1][i+(1<<j-1)]);
}
int LCP(int id,int x,int y){
    x=rk[id][x];y=rk[id][y];
    if (x>y) swap(x,y);x++;
    int k=lg[y-x+1];
    return min(RMQ[id][k][x],RMQ[id][k][y-(1<<k)+1]);
}
int main(){
    for (scanf("%d",&te);te;te--){
        scanf("%s",s+1);n=strlen(s+1);
        for (int i=1;i<=n;i++) t[i]=s[i];t[n+1]=0;
        reverse(t+1,t+1+n);
        MakeSA(0,s,n);MakeSA(1,t,n);
        for (int i=1;i<=n;i++) pre[i]=suf[i]=0;
        for (int i=1;i<=(n>>1);i++)
            for (int j=i,k=i+i;k<=n;j+=i,k+=i){
                int lcp=LCP(0,j,k)-1,lcs=LCP(1,n-j+1,n-k+1)-1;
                if (lcp+lcs<i-1) continue;
                int L=max(i-1-lcp,0),R=min(lcs,i-1);
                suf[j-R]++;suf[j-L+1]--;
                L=max(i-1-lcs,0);R=min(lcp,i-1);
                pre[k+L]++;pre[k+R+1]--;
            }
        for (int i=1;i<=n;i++) pre[i]+=pre[i-1],suf[i]+=suf[i-1];
        LL ans=0;
        for (int i=1;i<n;i++) ans+=(LL)pre[i]*suf[i+1];
        printf("%lld\n",ans);
    }
    return 0;
}