题解

95分的哈希做法

易得到$\sum\limits_{i=1}^{n-1}a_ib_{i+1}$即为答案,其中$a_i$为以$i$为结尾的$AA$串数量,$b_i$为以$i$为开头的$AA$串数量。

可以通过枚举$i$为中心,$O(n^2)$拿到不错的成绩

100分的后缀做法

尝试优化$a_i,b_i$的求解过程。

考虑枚举$A$的长度$l$,

枚举关键点$l,2l,3l,\ldots$

两个相邻的关键点之间肯定有些什么性质。

可以发现,一个$A$若经过其中一个关键点$x$,另一个$A$一定经过另外一个关键点$y$。

考虑这样的$A$有多少个。

画一画图,首先存在一个的话,必定有$lcp(x,y)+lcs(x,y)-1=l$

$s:suffix,p:pre$

大胆猜测一下,可以得到这两个关键点$x,y$之间存在一个区间$[L,R]$,使得前一个$A$的结尾落在区间$[L,R]$

通过某些差分转化(不好描述,但很容易理解)可以转化为95分解法中的结尾开头方案。

前缀和后缀就用后缀数组+ST表处理即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<map>
#include<cstdlib>
#include<vector> 
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
using namespace std;
const int N=30205,M=1e6+5,Max=2e5;
const ull p0=31,p1=37;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int n,lg[N];
void init(){for(int i=2;i<=30000;i++)lg[i]=lg[i>>1]+1;}
struct String
{
    int f[15][N];
    int sa[N],wv[N],wa[N],wb[N],rk[N],height[N],c[N],m;
    I bool cmp(int *y,int a,int b,int l){return y[a]==y[b]&&y[a+l]==y[b+l];}
    void SA(char *s)
    {
        int *x=wa,*y=wb,*t;
        memset(sa,0,sizeof(sa));memset(wa,0,sizeof(wa));memset(wb,0,sizeof(wb));
        m=100;for(int i=1;i<=m;i++)c[i]=0;
        for(int i=1;i<=n;i++)++c[x[i]=s[i]-'a'+1];
        for(int i=2;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;
        for(int j=1,p=0;p<n;j<<=1,m=p)
        {
            p=0;for(int i=n-j+1;i<=n;i++)y[++p]=i;
            for(int i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j;
            for(int i=1;i<=m;i++)c[i]=0;
            for(int i=1;i<=n;i++)++c[wv[i]=x[y[i]]];
            for(int i=2;i<=m;i++)c[i]+=c[i-1];
            for(int i=n;i>=1;i--)sa[c[wv[i]]--]=y[i];
            t=x;x=y;y=t;x[sa[1]]=1;p=1;
            for(int i=2;i<=n;i++)
                x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p:++p;
        }
        for(int i=1;i<=n;i++)rk[sa[i]]=i;
        for(int i=1,j=0,k=0;i<=n;height[rk[i++]]=k)
            for(k?k--:k,j=sa[rk[i]-1];s[i+k]==s[j+k];++k);
        for(int i=1;i<=n;i++)f[0][i]=height[i];
        for(int i=1;i<=lg[n];i++)
            for(int j=1;j+(1<<i)-1<=n;j++)
                f[i][j]=min(f[i-1][j],f[i-1][j+(1<<(i-1))]); 
    }
    I int query(int x,int y)
    {
        x=rk[x],y=rk[y];
        if(x>y)swap(x,y);x++;
        int l=lg[y-x+1];
        return min(f[l][x],f[l][y-(1<<l)+1]);
    }
}A,B;
int a[N],b[N];char s[N];
int main()
{
    int T;qr(T);
    init();
    while(T--)
    {
        memset(a,0,sizeof(a));memset(b,0,sizeof(b));
        scanf("%s",s+1);n=strlen(s+1);
        A.SA(s);
        reverse(s+1,s+n+1);
        B.SA(s);
        for(int l=1;l<=(n>>1);l++)
            for(int i=l,j=l+l;j<=n;i=j,j+=l)
            {
                int lcp=min(l,A.query(i,j)),lcs=min(l-1,B.query(n-i+2,n-j+2));
                if(lcp+lcs>=l)
                {
                    int t=lcp+lcs-l+1;
                    ++b[i-lcs];--b[i-lcs+t];
                    ++a[j+lcp-t];--a[j+lcp];
                }
                
            }
        for(int i=1;i<=n;i++)a[i]+=a[i-1],b[i]+=b[i-1];
        ll ans=0;
        for(int i=1;i<n;i++)ans+=1ll*a[i]*b[i+1];
        qw(ans);puts("");
    }
    return 0;
}
/*
1
ysvysvysvysvysvysvysvysvysvysvysvysvysvysvysvysvysvysv
*/