codeforces 835D Palindromic characteristics

​​ 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: 3. Its left half equals to its right half. 4. 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. Examples Input abba Output 6 1 0 0 Input abacaba Output 12 4 1 0 0 0 0 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. dp大概真的是博大精深了吧 能想一半 但总有个槛过不去qwq 我好菜啊 设dp[i][j]表示这个区间是几阶的回文 那么如果它是n阶回文 那么它一定也是n-1 n-2 n-3…1阶回文了 那我们预处理把长度1~2的都预处理出来 然后继续dp的时候 如果我现在是l~r这个区间 如果我l+!~r-1是一个回文了 那么如果我s[l]==s[r]那么我这个l~r这个区间也一定是个回文了 而且因为回文的性质我直接答案就是我区间的一半的阶+1就是我当前回文的阶了 然后每往上更新一次我 就可以算出这个回文对比他低阶的贡献了 依次加1即可 比如一个三阶的bbbb 它可以是1阶的 也可以是2阶的 bbbb->bb bb 也可以是三阶的bbbb->bb bb->b b

#include#include#define N 5500char s[N];int cnt[N],dp[N][N];int main(){ freopen("cf.in","r",stdin); scanf("%s",s+1);int n=strlen(s+1); for (int i=1;i<=n;++i){ dp[i][i]=1; ++cnt[1];if (i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。