3859: I Love Palindrome String
内存限制:128 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:1
解决:1
题目描述
You are given a string S=s1s2..s|S| containing only lowercase English letters. For each integer i∈[1,|S|] , please output how many substrings slsl+1...sr satisfy the following conditions:
∙ r−l+1 equals to i.
∙ The substring slsl+1...sr is a palindrome string.
∙ slsl+1...s⌊(l+r)/2⌋ is a palindrome string too.
|S| denotes the length of string S.
A palindrome string is a sequence of characters which reads the same backward as forward, such as madam or racecar or abba.
∙ r−l+1 equals to i.
∙ The substring slsl+1...sr is a palindrome string.
∙ slsl+1...s⌊(l+r)/2⌋ is a palindrome string too.
|S| denotes the length of string S.
A palindrome string is a sequence of characters which reads the same backward as forward, such as madam or racecar or abba.
输入
There are multiple test cases.
Each case starts with a line containing a string S(1≤|S|≤3×1e5) containing only lowercase English letters.
It is guaranteed that the sum of |S| in all test cases is no larger than 4×1e6.
Each case starts with a line containing a string S(1≤|S|≤3×1e5) containing only lowercase English letters.
It is guaranteed that the sum of |S| in all test cases is no larger than 4×1e6.
输出
For each test case, output one line containing |S| integers. Any two adjacent integers are separated by a space.
样例输入 复制
abababa
样例输出 复制
7 0 0 0 3 0 0