题意

给定一个字符串，定义 $k$ 回文串如下：

• 一个字符串是 $k$ 回文串，当且仅当它本身是回文串，且它的左半部分（非空）是 $(k-1)$ 回文串。
• 特别地，$0$ 回文串定义为任意字符串。

要求统计原字符串中所有子串中，分别是 $1$ 回文串、$2$ 回文串、…… 的子串数量。

思路

观察 I
如果一个字符串是 $k$ 回文串，那么它也是 $(k-1)$ 回文串。

观察 II
一个字符串是 $k$ 回文串，当且仅当同时满足以下两个条件：

1. 它本身是回文串。
2. 它的左半部分（非空）是 $(k-1)$ 回文串。

基于以上观察，我们可以通过动态规划求出每个子串的最大 $k$ 值，再通过后缀和统计答案。

算法步骤

1. 定义 $dp[l][r]$ 表示子串 $s[l..r]$ 的最大 $k$ 值（即它是 $k$ 回文串，但不是 $(k+1)$ 回文串）。
2. 按子串长度从小到大计算 $dp$ 值：
   • 当 $l = r$ 时，$dp[l][r] = 1$（单个字符是 $1$ 回文串）。
   • 当 $r - l = 1$ 时，若 $s[l] = s[r]$，则 $dp[l][r] = 2$，否则为 $0$。
   • 当 $r - l > 1$ 时：
     • 如果 $s[l] \neq s[r]$ 或 $dp[l+1][r-1] = 0$，则 $dp[l][r] = 0$。
     • 否则，令 $m = \lceil (l + r) / 2 \rceil - 1$，则 $dp[l][r] = dp[l][m] + 1$。
3. 统计 $cnt[k]$ 表示 $dp$ 值恰好为 $k$ 的子串个数。
4. 计算 $ans[k] = \sum_{i=k}^{|s|} cnt[i]$，即所有是 $k$ 回文串的子串数量。

复杂度分析

• 时间复杂度：$O(|s|^2)$，因为需要枚举所有子串并计算 $dp$ 值。
• 空间复杂度：$O(|s|^2)$，用于存储 $dp$ 数组。

优化方案
注意到字符串最多是 $\lfloor \log_2 |s| \rfloor$ 回文串，因此可以将时间复杂度优化为 $O(|s|^2 \log |s|)$，同时将空间复杂度降低到 $O(|s|)$。

代码说明

• 使用二维数组 $dp$ 存储每个子串的最大 $k$ 值。
• 按长度递增顺序计算，利用已计算出的较短子串结果。
• 最后通过后缀和统计每个 $k$ 对应的子串数量。

#include<bits/stdc++.h>
#define re register
#define ull unsigned long long
using namespace std;
char c[5005];
ull fac,fro,bac;
/*
fac计算base的幂
fro计算从前往后的哈希值
bac计算从后往前的哈希值
这里是直接推过去的，也可以预处理一遍
*/
int n,dp[5005],ans[5005];
int main(){
  scanf("%s",c),n=strlen(c);
  //注意要把可能影响后面答案的dp清零（也可直接把dp开两维）
  for(re int j=0;j<n;dp[j++]=0){
    fro=bac=0,fac=1;
    for(re int i=j;i<n;++i){
      dp[i]=0,fro=fro*131+c[i],bac=bac+fac*c[i],fac=fac*131;
      fro^bac?0:++ans[dp[i]=dp[(i-j-1>>1)+j]+1];
    }
  }
  for(re int i=n;i;--i)ans[i]+=ans[i+1];//后缀和
  for(re int i=1;i<=n;++i)printf("%d ",ans[i]);
}