题解 CF835D 【Palindromic characteristics】

xzggzh1 · 2021-01-29 17:42:28 · 题解

和已有的一篇回文自动机的解法不同，这里给出的是简单的 n\leq 5000 的解法，做法是 dp。

题意：

给你一个串，让你求出 k 阶回文子串有多少个。其中：

1. 如果一个字串是 k 阶回文，那他一定还是 k-1 阶回文。
2. 如果一个串是 k 阶回文，那么这个串需要满足：它本是是回文的且他的左半部分是 k-1 回文的（如果长度是奇数，则左半部分长度向下取整）。

题目中 n\leq 5000，直接考虑二维 dp 。

设 dp[i][j] 表示 s[i...j] 的回文阶数，若为 0 则不是回文串。

考虑从 dp[i+1][j-1] 到 dp[i][j] 的转移：

若 s[i] \not = s[j] 或者 dp[i+1][j-1]=0 那么 dp[i][j]=0 。

否则 dp[i][j]=dp[i][i+(i-j+1)/2-1]+1 。（等于左半部分的阶数 +1 ）。

知道转移，最后记得搞个前缀和就好了，这里是核心代码。

int main(){
    scanf("%s",s+1);n=strlen(s+1);
    for(int i=1;i<=n;++i) dp[i][i]=1,ans[1]++;
    for(int len=2;len<=n;++len)
    for(int i=1,j=i+len-1;i+len-1<=n;++i,ans[dp[i][j]]+=(bool)dp[i][j],j=i+len-1)
    if(s[i]!=s[j]||i+1<=j-1&&dp[i+1][j-1]==0) dp[i][j]=0;
    else dp[i][j]=dp[i][i+len/2-1]+1;
    for(int i=n;i>=1;--i) ans[i]+=ans[i+1];
    for(int i=1;i<=n;++i) printf("%d ",ans[i]);
}