【Codeforces Round #427 (Div. 2) D】Palindromic characteristics

【Link】:http://codeforces.com/contest/835/problem/D

【Description】

给你一个字符串;
让你在其中找到1..k阶的回文子串;
并统计它们的数量
如果一个字符串是一个回文串,则它可以是1阶子串;
k阶字符串,要求它的左边和右边都是k-1阶子串;

【Solution】

bo[i][j]表示i..j这一段是否为回文;
可以用O(n2)的复杂度处理出整个bo数组;
然后O(n2)枚举每一段区间;
算出这个区间的字符串最大可以是一个几阶字符串记为k;
ans[k]++;
如何算?
递归！
void getk(int l,int r)
如果l..r这一段不是回文,则直接返回0;
可以认为他是”0”阶子串;
如果l..r这一段是回文;
那么就只要在l..mid和mid..r这两段中选一段;
再递归求它的字符串阶数+1就好了;
不用两个都算!
则这里复杂度为O(log2n)
总的复杂度为O(n2log2n)
最后;
阶数为i的字符串也被认为是阶数为1..i的字符串;
所以
for (int i = n-1;i >= 1;i–)
ans[i]+=ans[i+1];

【NumberOf WA】

2

【Reviw】

我一开始,想的是,从低阶的字符串推出高阶的字符串
没有考虑到,这样增长得是很快的;
竟然没有想到逆向..

【Code】

#include <bits/stdc++.h>
using namespace std;

const int N = 5e3;

char s[N+10];
int n,bo[N+10][N+10],ans[N+10];
//int dp[N+10][N+10];

int getk(int l,int r){
    if (!bo[l][r]) return 0;
    if (l==r) return 1;
    if (l+1==r) return 2;
    int len = (r-l+1)/2;
    int L = l,R = r;
    return getk(L,L+len-1)+1;
}

int main(){
//    memset(dp,255,sizeof dp);
    scanf("%s",s+1);
    n = strlen(s+1);

    for (int i = 1;i <= n;i++){
        bo[i][i] = 1;
        if (i+1 <= n && s[i]==s[i+1]) bo[i][i+1] = 1;
    }
    for (int i = 3;i <= n;i++){
        for (int j = 1;j <= n;j++){
            int r = j + i - 1;
            if (r > n) break;
            if (bo[j+1][r-1] && s[j]==s[r]) bo[j][r] = 1;
        }
    }

    for (int i = 1;i <= n;i++)
        for (int j = i;j <= n;j++){
            ans[getk(i,j)]++;
        }
    for (int i = n-1;i >= 1;i--)
        ans[i]+=ans[i+1];
    for (int i = 1;i <= n;i++)
        printf("%d ",ans[i]);
    return 0;
}