9050: String Magic (Hard Version)

内存限制:512 MB 时间限制:5 S
题面:传统 评测方式:文本比较 上传者:
提交:2 通过:1

题目描述

Z is learning string theory and he finds a difficult problem. Given a string S of length n (indexed from 1 to n) , define f(S) equal to the number of pair (i, j) that:
 • 1 ≤ i < j ≤ n • j − i + 1 = 2k, k > 0 (j − i + 1 is even) 
• S[i, i + k − 1] = S[i + k, j] • S[i, i + k − 1] is a palindrome 
Here S[L, R] denotes the substring of S with index from L to R.
 A palindrome is a string that reads the same from left to right as from right to left. To solve this problem, Z needs to calculate f(S[1, i]) for each 1 ≤ i ≤ n. He doesn’t know how to solve it, but he knows it’s easy for you. Please help him.

输入格式

The first line contains one integer T (1 ≤ T ≤ 10) which represents the number of test cases. For each test case: One line contains a string S (1 ≤ |S| ≤ 105 ). It’s guaranteed that the string only contains lowercase letters.

输出格式

For each test case: Print one line containing n integers, represents f(S[1, i]) for each 1 ≤ i ≤ n.

输入样例 复制

3
aaaa
abaaba
ababa

输出样例 复制

0 1 2 4
0 0 0 1 1 2
0 0 0 0 0