P9282 [AGM 2023 资格赛] 回文

· · 题解

题目分析

本题核心是一个只要你学过回文树就知道的定理：一个长度为 n 的字符串，本质不同回文子串的个数最多只有 n 个。

根据题目这个条件：如果 x 是回文串，那么假设 y 是 x 的前 \frac{|x|+1}{2} 个字符组成的字符串 f(x)=f(y)+1，可知：

那么大致思路就出来了：枚举所有本质不同的回文串，分别对每种回文串 x，暴力递归求 f(x)（顺便记忆化一下），然后再计算出每种回文串在原串中出现了多少次，假设结果是 cnt_x，那么答案就可以这么计算： ans_{f_x} \gets ans_{f_x} + cnt_x。

这里提供一个使用回文树的实现方法：

int st[N][LOGN];
void init_ST()
{
    int i,j;
    for(i=2;i<tot;i++)
    {
        st[i][0]=fail[i];
        for(j=1;j<LOGN;j++)
        {
            st[i][j]=st[st[i][j-1]][j-1];
        }
    }
}
int get_substr(int l,int r)
{
    int now,tmp,i;
    now=pos[r];// pos[r] 表示以r为结尾的最长回文子串在回文树上的节点编号 

    // 倍增往fail跳 
    for(i=LOGN-1;~i;i--)
    {
        if(len[st[now][i]]>=r-l+1) now=st[now][i];
    }
    return now;
}
void count()
{
    // 计算每种回文串的出现次数 
    for(int i=tot-1;i;i--) cnt[fail[i]]+=cnt[i];
}
int f[MAX];
int dfs(int l,int r)// 记忆化求f(x) 
{
    // 获取子串[l,r]在回文树上的节点编号
    // 这里我用了倍增，似乎不用倍增也能过
    int now=get_substr(l,r);

    if(r-len[now]+1!=l) return 0; // 如果子串[l,r]不是回文串 f(x)=0 
    if(len[now]==1) return f[now]=1;
    if(len[now]<=0) return 0;// len[now]<=0 说明 now 是根节点 
    if(f[now]!=-1) return f[now];
    f[now]=dfs(l,r-len[now]/2)+1;
    return f[now];
}
ll ans[35];
void work(int n,int k)
{
    int i,l,r,now;
    count();
    init_ST();
    memset(f,-1,sizeof f);
    memset(ans,0,sizeof ans);
    for(i=1;i<=n;i++)
    {
        l=i-len[pos[i]]+1;
        r=i;
        // 以i为结尾的最长回文子串是[l,r]

        /*
          这里为什么不需要枚举所有以i为结尾的回文串？
           - 回文树的每个节点代表一种回文串
           - 每次往回文树中新加入一个字符，最多只会创建一个新的节点
          所以只需要求新的节点的f(x)即可
        */
        dfs(l,r);
    }
    for(i=2;i<tot;i++) ans[f[i]]+=cnt[i];
    for(i=1;i<=k;i++) printf("%lld%c",ans[i]," \n"[i==k]);
}

记忆化求 f(x) 的部分时间复杂度是 O(n) 的，每次倍增找回文子串，时间复杂度 O(\log n)，所以总时间复杂度为 O(n \log n)。