D. Palindromic characteristics

Codeforces

IDCF835D

Time3000ms

Memory256MB

Difficulty—

brute forcedphashingstrings

English · Original

Chinese · Translation

Formal · Original

Palindromic characteristics of string _s_ with length |_s_| is a sequence of |_s_| integers, where _k_\-th number is the total number of non-empty substrings of _s_ which are _k_\-palindromes. A string is 1\-palindrome if and only if it reads the same backward as forward. A string is _k_\-palindrome (_k_ > 1) if and only if: 1. Its left half equals to its right half. 2. Its left and right halfs are non-empty (_k_ - 1)-palindromes. The left half of string _t_ is its prefix of length ⌊|_t_| / 2⌋, and right half — the suffix of the same length. ⌊|_t_| / 2⌋ denotes the length of string _t_ divided by 2, rounded down. Note that each substring is counted as many times as it appears in the string. For example, in the string "aaa" the substring "a" appears 3 times. ## Input The first line contains the string _s_ (1 ≤ |_s_| ≤ 5000) consisting of lowercase English letters. ## Output Print |_s_| integers — palindromic characteristics of string _s_. [samples] ## Note In the first example 1-palindromes are substring «a», «b», «b», «a», «bb», «abba», the substring «bb» is 2-palindrome. There are no 3- and 4-palindromes here.

字符串 #cf_span[s]（长度为 #cf_span[|s|]）的回文特征是一个包含 #cf_span[|s|] 个整数的序列，其中第 #cf_span[k] 个数表示 #cf_span[s] 中所有是 #cf_span[k]-回文串的非空子串的总数。一个字符串是 #cf_span[1]-回文串，当且仅当它正读和反读完全相同。一个字符串是 #cf_span[k]-回文串（#cf_span[k > 1]），当且仅当：字符串 #cf_span[t] 的左半部分是其长度为 #cf_span[⌊|t| / 2⌋] 的前缀，右半部分是其长度相同的后缀。#cf_span[⌊|t| / 2⌋] 表示字符串 #cf_span[t] 的长度除以 #cf_span[2] 后向下取整的结果。注意，每个子串根据其在字符串中出现的次数被重复计数。例如，在字符串 "aaa" 中，子串 "a" 出现了 3 次。第一行包含一个由小写英文字母组成的字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 5000]）。请输出 #cf_span[|s|] 个整数——字符串 #cf_span[s] 的回文特征。在第一个例子中，1-回文串是子串 «a»、«b»、«b»、«a»、«bb»、«abba»，子串 «bb» 是 2-回文串。这里不存在 3-回文串和 4-回文串。 ## Input 第一行包含一个由小写英文字母组成的字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 5000]）。 ## Output 请输出 #cf_span[|s|] 个整数——字符串 #cf_span[s] 的回文特征。 [samples] ## Note 在第一个例子中，1-回文串是子串 «a»、«b»、«b»、«a»、«bb»、«abba»，子串 «bb» 是 2-回文串。这里不存在 3-回文串和 4-回文串。

**Definitions** Let $ s $ be a string of length $ n = |s| $, with $ s[i] \in \{a, b, \dots, z\} $ for $ i \in \{1, \dots, n\} $. For $ k \in \mathbb{Z}^+ $, a non-empty substring $ t = s[i:j] $ (with $ 1 \leq i \leq j \leq n $) is a **$ k $-palindrome** if: - $ k = 1 $: $ t $ is a palindrome, i.e., $ t_\ell = t_{|t|+1-\ell} $ for all $ \ell \in \{1, \dots, |t|\} $. - $ k > 1 $: (i) $ t $ is a palindrome, and (ii) the left half of $ t $, defined as the prefix of length $ \left\lfloor \frac{|t|}{2} \right\rfloor $, is a $ (k-1) $-palindrome. Let $ P_k \subseteq \{ s[i:j] \mid 1 \leq i \leq j \leq n \} $ be the set of all $ k $-palindromic substrings of $ s $. **Constraints** $ 1 \leq n = |s| \leq 5000 $ **Objective** Compute the sequence $ (c_1, c_2, \dots, c_n) $, where for each $ k \in \{1, \dots, n\} $: $$ c_k = |P_k| $$ i.e., $ c_k $ is the total number of non-empty substrings of $ s $ that are $ k $-palindromes. Output $ c_1, c_2, \dots, c_n $.

Samples

Input #1

abba

Output #1

6 1 0 0

Input #2

abacaba

Output #2

12 4 1 0 0 0 0

API Response (JSON)

{
  "problem": {
    "name": "D. Palindromic characteristics",
    "description": {
      "content": "Palindromic characteristics of string _s_ with length |_s_| is a sequence of |_s_| integers, where _k_\\-th number is the total number of non-empty substrings of _s_ which are _k_\\-palindromes. A stri",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF835D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Palindromic characteristics of string _s_ with length |_s_| is a sequence of |_s_| integers, where _k_\\-th number is the total number of non-empty substrings of _s_ which are _k_\\-palindromes.\n\nA stri...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "字符串 #cf_span[s]（长度为 #cf_span[|s|]）的回文特征是一个包含 #cf_span[|s|] 个整数的序列，其中第 #cf_span[k] 个数表示 #cf_span[s] 中所有是 #cf_span[k]-回文串的非空子串的总数。\n\n一个字符串是 #cf_span[1]-回文串，当且仅当它正读和反读完全相同。\n\n一个字符串是 #cf_span[k]-回文串（#cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s $ be a string of length $ n = |s| $, with $ s[i] \\in \\{a, b, \\dots, z\\} $ for $ i \\in \\{1, \\dots, n\\} $.  \nFor $ k \\in \\mathbb{Z}^+ $, a non-empty substring $ t = s[i:j] $ (w...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments