14328: 【原4328】回文特征

题目

题目描述

author: codeforces 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4328

Description

长为$|s|$的字符串$s$的回文特征是一个长为的序列，其中第k个数是s的非空k阶回文子串的数量。

一个字符串是一阶回文的当且仅当他正着和反着读是一样的。

一个字符串是k阶回文的($k > 1$)当且仅当：

1. 他的左半边和右半边一样
2. 他的左半边和右半边都是$k - 1$阶回文的。

一个串$t$的左半边定义为串的长为$\lfloor |t|/2 \rfloor$的前缀。一个串$t$的右半边定义为串的长为$\lfloor |t|/2 \rfloor$的后缀。

注意，统计数量时，有多少个子串符合条件就统计多少次，例如:'aaa'中,'a'就出现了3次，应该都被统计进去。

Input Format

一行，包含长为$|s|$的小写英文字符串$s$。($1 \leq |s| \leq 5000$)

Output Format

输出s的回文特征。(长为$|s|$，用一个空格隔开)

Sample Input 1

abba

Sample Output 1

6 1 0 0

Sample Input 2

abacaba

Sample Output 2

12 4 1 0 0 0 0

Note

在第一个样例中，1阶回文串为 «a», «b», «b», «a», «bb», «abba», <> 是二阶回文串。没有3阶和4阶回文串。

zqy2018's solution

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
char s[5005];
int ord[5005][5005] = {0};
int cnt[5005] = {0};
void init(){
    scanf("%s", s);
}
void solve(){
    int n = strlen(s);
    int hf = (n >> 1);
    REP(i, 0, n - 1)
        ord[i][i] = ord[i + 1][i] = 1;
    cnt[1] = n;
    REP(l, 1, hf){
        REP(i, l, n - l - 1){
            if (ord[i - l + 1][i + l - 1] && s[i - l] == s[i + l])
                ord[i - l][i + l] = ord[i + 1][i + l] + 1, 
                ++cnt[ord[i - l][i + l]];
        }
        REP(i, l - 1, n - l - 1){
            if (ord[i - l + 2][i + l - 1] && s[i - l + 1] == s[i + l]){
                ord[i - l + 1][i + l] = ord[i + 1][i + l] + 1, 
                ++cnt[ord[i - l + 1][i + l]];
            }
        }
    }
    REPR(i, n - 1, 1)
        cnt[i] += cnt[i + 1];
    REP(i, 1, n - 1)
        printf("%d ", cnt[i]);
    printf("%d\n", cnt[n]);
}
int main(){
    init();
    solve();
    return 0;
}