题目描述

难度分:$1900$

输入长度$\leq 5000$的字符串$s$，只包含小写英文字母。

如果字符串$s$是回文串，我们称$s$为$1$阶回文串。如果字符串$s$的左半部分等于$s$的右半部分，且左半部分和右半部分都是$k-1$阶回文串，我们称$s$为$k$阶回文串（$k \gt 1$）。

注：设$m = \lfloor \frac{|s|}{2} \rfloor$，其中$|s|$表示$s$串的长度。「左半部分」指$s$的长为$m$的前缀，「右半部分」指$s$的长为$m$的后缀。

输出$n$个数，分别表示$s$的$1,2,3,…,n$阶非空回文子串的个数。

输入样例$1$

abba

输出样例$1$

6 1 0 0 

输入样例$2$

abacaba

输出样例$2$

12 4 1 0 0 0 0 

算法

动态规划+字符串哈希

注意到一个细节，一个$k$阶回文串需要两个$k-1$阶回文串才能构成。因此随着阶数增大，回文串的长度是指数级别递增，那么数量就会骤降，要不了多少次就会出现数量为$0$的回文串阶数。

状态定义

$f[l][r][k]$表示$[l,r]$是不是$k$阶回文串。先来个经典的区间DP可以求出$k=1$时的矩阵。

状态转移

遍历$k \in [2,n]$，枚举$r \in [1,n]$，对于给定的子串右端点，枚举$c \in [1,r]$。如果当前阶的回文串长度为奇数，那么$m=r-c$，$l=c-m$，只要$f[l][c-1][k-1]=f[c+1][r][k-1]=$true，且$[l,c-1]$和$[c+1,r]$两个串相等，那$[l,r]$就是$k$阶回文串$f[l][r][k]=$true。判断两个子串是否相等可以用字符串哈希对$s$做完预处理后$O(1)$判断。

复杂度分析

时间复杂度

由于阶数走$O(log_2k)$级别的步数就会让后面阶数的回文串都是$0$个，所以遍历$k$的时候时间复杂度为$O(log_2k)$。而对于给定的阶数，$O(n^2)$进行动态规划填$f[l][r][k]$。所以整个算法的时间复杂度为$O(n^2log_2k)$。

空间复杂度

由于$k$阶的状态只取决于$k-1$阶的状态，所以DP矩阵$f$可以用滚动数组把$k$那一维优化掉，空间复杂度为$O(n^2)$。因此，字符串哈希的空间复杂度为$O(n)$，DP矩阵的空间复杂度为$O(n^2)$，后者是瓶颈，也是整个算法的额外空间复杂度。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ULL;

const int N = 5010, base = 131;
int n;
ULL p[N], h[N];
bool f[N][N][2];
char s[N];

void init() {
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++) {
            f[i][j][0] = f[i][j][1] = false;
        }
    }
}

ULL shash(int left, int right, bool is_rev=false) {
    return h[right] - h[left - 1]*p[right - left + 1];
}

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    init();
    p[0] = 1;
    for(int i = 1; i <= n; i++) {
        h[i] = h[i - 1]*base + s[i];
        p[i] = p[i - 1]*base;
    }
    for(int i = 1; i <= n; i++) {
        f[i][i][1] = true;
        if(i + 1 <= n && s[i] == s[i + 1]) {
            f[i][i + 1][1] = true;
        }
    }
    for(int len = 3; len <= n; len++) {
        for(int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            if(s[l] == s[r]) {
                f[l][r][1] = f[l + 1][r - 1][1];
            }
        }
    }
    int cnt = 0;
    for(int l = 1; l <= n; l++) {
        for(int r = l; r <= n; r++) {
            if(f[l][r][1]) cnt++;
        }
    }
    printf("%d ", cnt);
    for(int k = 2; k <= n; k++) {
        if(cnt == 0) {
            printf("%d ", 0);
        }else {
            int index = k % 2;
            for(int r = 2; r <= n; r++) {
                for(int c = r; c >= 1; c--) {
                    int half = r - c, l = c - half;
                    // [l,r]是奇数长度，c为正中心
                    if(r - c == c - l && shash(l, c - 1) == shash(c + 1, r) && f[l][c - 1][index^1] && f[c + 1][r][index^1]) {
                        f[l][r][index] = true;
                    }
                    half = r - c + 1, l = c - half;
                    // [l,r]是偶数长度
                    if(r - c + 1 == c - l && shash(l, c - 1) == shash(c, r) && f[l][c - 1][index^1] && f[c][r][index^1]) {
                        f[l][r][index] = true;
                    }
                }
            }
            cnt = 0;
            for(int l = 1; l <= n; l++) {
                for(int r = l; r <= n; r++) {
                    if(f[l][r][index]) cnt++;
                    f[l][r][index^1] = false;
                }
            }
            printf("%d ", cnt);
        }
    }
    return 0;
}