传送门

「优秀的拆分」可以说是非常优秀了

温馨提示:后缀数组多测要清空$tp$数组!!!!

设$st[i]$为以第$i$个字符为开头,能有多少个$AA$串;$en[i]$即以第$i$个字符为结尾,有多少个$AA$串。

答案就是$\sum\limits_{i=1}^{n-1}en[i]*st[i+1]$。我们就能用哈希(蒟蒻不会哈希只能强上$SA$)$O(n^2)$得到$95$分的好成绩。

(如果蒟蒻比赛写到这就懒得继续写了,散了散了)

枚举每个$A$串长度$len$,对母串每$len$个字符打一个标记,显然一个$AA$串一定覆盖两个标记。那么对于每两个相邻的标记,若它们的$LCS+LCP\ge len$就能产生$AA$串。($LCS$是前缀的最长公共后缀,$LCP$是后缀的最长公共前缀)

并且这个$AA$串左右端点可以移动,移动范围为$LCS+LCP-len$,给这段区间$+1$,上差分。

时间复杂度$O(\sum\limits_{i=1}^{n}\frac{n}{i})=O(n\log n)$

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 30005
#define inf 0x3f3f3f3f

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int lg[maxn],n,m;
long long st[maxn],en[maxn];
struct Suffix_Array{
    int sa[maxn],rk[maxn],tp[maxn],tax[maxn],hei[maxn],f[maxn][25];
    char s[maxn];
    void Rsort(){
        for(register int i=0;i<=m;++i)tax[i]=0;
        for(register int i=1;i<=n;++i)++tax[rk[i]];
        for(register int i=1;i<=m;++i)tax[i]+=tax[i-1];
        for(register int i=n;i;--i)sa[tax[rk[tp[i]]]--]=tp[i];
    }
    void Ssort(){
        for(register int i=1;i<=n;++i)rk[i]=s[i],tp[i]=i;
        m=225,Rsort();
        for(register int k=1,p=0;p<n;m=p,k<<=1){
            p=0;
            for(register int i=1;i<=k;++i)tp[++p]=n-k+i;
            for(register int i=1;i<=n;++i)if(sa[i]>k)tp[++p]=sa[i]-k;
            Rsort();
            for(register int i=1;i<=n;++i)tp[i]=rk[i];
            rk[sa[1]]=p=1;
            for(register int i=2;i<=n;++i)
                rk[sa[i]]=tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k]?p:++p;
        }
    }
    void get_height(){
        int k=0,x;
        for(register int i=1;i<=n;++i){
            if(rk[i]==1)continue;
            if(k)--k;
            x=sa[rk[i]-1];
            while(i+k<=n&&x+k<=n&&s[i+k]==s[x+k])++k;
            hei[rk[i]]=k;
        }
    }
    void ST(){
        for(register int i=1;i<=n;++i)f[i][0]=hei[i];
        for(register int j=1;j<lg[n];++j)
            for(register int i=1;i+(1<<j)-1<=n;++i)
                f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    }
    inline int query(int l,int r){
        int len=lg[r-l+1]-1;
        return min(f[l][len],f[r-(1<<len)+1][len]);    
    }
    inline int lcp(int i,int j){
        return query(min(rk[i],rk[j])+1,max(rk[i],rk[j]));
    }
    void init(){
        memset(tp,0,sizeof tp);
        Ssort(),get_height(),ST();
    }
}pre,suf;
inline void add(int l,int r,long long *a){
    if(r<1)return;
    if(l<=n)++a[max(l,1)];
    if(r<n)--a[r+1];
}
inline int LCS(int x,int y){
    if(!x||!y)return 0;
    return pre.lcp(n-x+1,n-y+1);
}
inline int LCP(int x,int y){
    return suf.lcp(x,y);
}
int main(){
    int t=read();
    long long ans;
    for(register int i=1;i<maxn;++i)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    while(t--){
        scanf("%s",suf.s+1),n=strlen(suf.s+1),ans=0;
        memset(st,0,sizeof st),memset(en,0,sizeof en);
        for(register int i=1,j=n;i<=n;--j,++i)pre.s[i]=suf.s[j];
        pre.init(),suf.init();
        for(register int i=1;i<=(n>>1);++i){
            for(register int j=i+i;j<=n;j+=i){
                int lcs=min(LCS(j-1,j-i-1),i-1),lcp=min(LCP(j,j-i),i),delta=lcs+lcp-i;
                if(lcs+lcp<i)continue;
                add(j-i-lcs,j-i-lcs+delta,st),add(j+lcp-1-delta,j+lcp-1,en);
            }
        }
        for(register int i=2;i<=n;++i)
            st[i]+=st[i-1],en[i]+=en[i-1];
        for(register int i=1;i<n;++i)
            ans+=en[i]*st[i+1];
        printf("%lld\n",ans);
    }
}

后记:

数据千万条,清空第一条。

多测不清空,爆零两行泪。

$SA$要清空$tp$数组。。。蒟蒻调了一小时才发现的$QAQ$

还有蒟蒻想知道$LCS$有没有简便一点的$O(1)$求法。翻转字符串造$SA$感觉太暴力了。。。