【题意】

能被表示为AABB的形式被称为一种优秀的拆分，求一个字符串有多少个不同的优秀的拆分

注意本质相同的子串在不同位置要重复计算

【分析】

首先我们不难想到计算f[i]表示i为结尾的AA形式的个数,g[i]表示i开头的AA形式的个数

答案就为f[i]*g[i+1] i=1-(n-1)

问题就变成了如何快速的求出f和g

我们可以通过哈希的方式$O(n^2)$暴力算出每个位置的f和g，这样做可以得到95分的好成绩

那么谁还在乎正解啊

【95pts代码】

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define lson now<<1
#define rson now<<1|1
typedef long long ll;
const int maxn=2005;
ll f[maxn],g[maxn];
char s[maxn];
const int mod=1e9+7;
const int base=2333;
int h[maxn],len,p[maxn];
void init()
{
    for(int i=1;i<=len;i++)
        h[i]=(1LL*h[i-1]*base+s[i]-'a')%mod;
}
int get(int l,int r)
{
    return (h[r]-1LL*h[l-1]*p[r-l+1]%mod+mod)%mod;
}
int main()
{
    int t;
    scanf("%d",&t);
    p[0]=1;
    for(int i=1;i<=2005;i++) p[i]=1LL*p[i-1]*base%mod;
    while(t--)
    {
        scanf("%s",s+1);
        len=strlen(s+1);
        for(int i=1;i<=len;i++) f[i]=g[i]=0;
        init();
        for(int i=2;i<=len;i++)
            for(int j=1;j<=(i/2);j++)
                if(get(i-2*j+1,i-j)==get(i-j+1,i))
                    f[i]++;
        for(int i=1;i<len;i++)
            for(int j=1;j<=(len-i+1)/2;j++)
                if(get(i,i+j-1)==get(i+j,i+2*j-1))
                    g[i]++;
        ll ans=0;
        for(int i=1;i<len;i++) ans+=1LL*f[i]*g[i+1];
        printf("%lld\n",ans);
    }
    return 0;
}

 

正解的方法就很神仙了，不知道怎么想到建立关键点

枚举AA中A的长度len，然后把整个字符串中长度为len的倍数的位置设立成关键点

这样每个AA一定会经过两个关键点，设这两个关键点为i,j，满足j=i+len

我们计算出lcp=lcp(suf(i),suf(j))，lcs=lcs(pre(i),pre(j))

简单画一下图就可以发现，当i-j中间的lcp和lcs没有交点就是存在AA

而重叠的部分就是AA串可以挪动的长度

我们利用这一点就可以打一下差分标记计算f,g了

时间复杂度$O(nlogn)$由于后缀数组和调和级数都是一只log

【参考代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define fi first
#define se second
const int maxn=3e4+5;
char a[maxn];
int n;
int lg[maxn];
struct SA
{
    int sa[maxn],rk[maxn],oldrk[maxn];
    int fz[maxn],cnt[maxn],id[maxn];
    int h[maxn];
    bool cmp(int x,int y,int w)
    {
        return  oldrk[x]==oldrk[y] && oldrk[x+w]==oldrk[w+y];
    }
    void build()
    {
        int m=233;
        for(int i=0;i<=m;i++) cnt[i]=0;
        for(int i=1;i<=n;i++) cnt[rk[i]=a[i]]++;
        for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;i--) sa[cnt[rk[i]]--]=i;
        int i,p;
        for(int 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=0;i<=m;i++) cnt[i]=0;
            for(i=1;i<=n;i++) cnt[fz[i]=rk[id[i]]]++;
            for(i=1;i<=m;i++) cnt[i]+=cnt[i-1];
            for(i=n;i>=1;i--) sa[cnt[fz[i]]--]=id[i];
            for(i=1;i<=n;i++) oldrk[i]=rk[i];
            for(p=0,i=1;i<=n;i++) rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
            if(n==p)
            {
                for(i=1;i<=n;i++) sa[rk[i]]=i;
                break;
            }
        }
        int k=0;
        for(int i=1;i<=n;i++)
        {
            if(k) k--;
            while(a[i+k]==a[sa[rk[i]-1]+k]) k++;
            h[rk[i]]=k;
        }       
    }
    int st[maxn][17];
    void ST_init()
    {
        memset(st,63,sizeof(st));
        for(int i=1;i<=n;i++) st[i][0]=h[i];
        for(int i=1;i<=16;i++)
            for(int j=1;j<=n;j++)
                st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
        
        // memset(st, 63, sizeof(st)); 
        // for (int i = 1; i <= n; i++) st[i][0]= h[i],printf("%d ",h[i]);; 
        // for (int j = 1; j <= 15; j++)
        //     for (int i = 1; i <= n; i++)
        //         st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); 
       
    }
    int query(int l,int r)
    {
        int ll=min(rk[l],rk[r])+1,rr=max(rk[l],rk[r]);
        int i=lg[rr-ll+1];
        return min(st[ll][i],st[rr-(1<<i)+1][i]);
    }
}A,B;
int f[maxn],g[maxn];
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    lg[0]=-1;
    for(int i=1;i<maxn;i++) lg[i]=lg[i>>1]+1;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",a+1);
        n=strlen(a+1);
        A.build(); A.ST_init();
        reverse(a+1,a+n+1);
        B.build(); B.ST_init();
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        for(int len=1;len<=n/2;len++)
            for(int i=len,j=i+len;j<=n;j+=len,i+=len)
            {
                int lcp=min(A.query(i,j),len),lcs=min(B.query(n-i +2,n-j+2),len-1); 
                // printf("%d %d\n",A.query(i,j),B.query(n-i +2,n-j+2));
                int t=lcs+lcp-len+1;
                if(lcs+lcp>=len)
                {
                    g[i-lcs]++; g[i-lcs+t]--;
                    f[j+lcp-t]++; f[j+lcp]--;
                }
            }
        for(int i=1;i<=n;i++) f[i]+=f[i-1],g[i]+=g[i-1];
        ll ans=0;
        // for(int i=1;i<=n;i++) printf("%d ",A.h[i]);
        // printf("\n");
        // for(int i=1;i<=n;i++) printf("%d ",B.h[i]);
        // printf("\n");        
        for(int i=1;i<n;i++) ans+=1ll*f[i]*g[i+1];
        printf("%lld\n",ans);
    }
    return 0;
}