Palindromic Characteristics

求一个字符串 $s$ 的所有子串中，对于所有 $1 \leq k \leq |s|$ ，" $k$ 重回文"的数量（ $k$ 重回文定义看原题）。

观察：

$k$ 重回文一定也是 $k-1$ 重回文
$k \leq \log|s|$

生成所有子串 $O(n^2)$ ，对每个子串判断是几重回文 $O(\log n)$ 。

判断几重回文的办法，是建前向和后向的哈希数组，然后比较两个方向的哈希值是否相等。然后缩小范围到前一半，再次判断是否是回文，每成功一次 $k$ 加一。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;
const int MAXN = 5005;
char s[MAXN];
int h[MAXN], H[MAXN], p[MAXN]; // H[] is reversed
const int A = 911382323, M = 972663749;
// const int A = 69420, M = 1e9+9;      // this WA on case 48 due to collision
int ans[25];
 
int main() {
    scanf("%s", s);
    n = strlen(s);
 
    p[0] = 1; h[0] = s[0]; 
    for (int i = 1; i < n; i++) {
        p[i] = (ll)p[i-1] * A % M;
        h[i] = ((ll)h[i-1] * A + s[i]) % M;
    }
    H[n-1] = s[n-1];
    for (int i = n-2; i >= 0; i--)
        H[i] = ((ll)H[i+1] * A + s[i]) % M;
 
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) {
            int b = j;
            int lvl = 0;
            for (int k = 1; k < 20; k++) {
                // check is [i,b] is palindromic
                int hash1 = i == 0 ? h[b] : (h[b] - (ll)h[i-1] * p[b-i+1] + (ll)M * p[b-i+1]) % M;
                int hash2 = b == n-1 ? H[i] : (H[i] - (ll)H[b+1] * p[b-i+1] + (ll)M * p[b-i+1]) % M;
                if (hash1 != hash2)
                    break;
                lvl = k;
                b = i + (b-i+1)/2 - 1;
                if (b < i) break;
            }
            for (int q = 1; q <= lvl; q++)
                ans[q]++;
        }
    for (int i = 1; i <= n; i++)
        printf("%d ", i < 20 ? ans[i] : 0);
    return 0;
}