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:   Its left half equals to its right half.  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.

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Complete search

String algorithms


Solutions:
def main():
	s = input()
	n = len(s)
	dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
	count = [0 for i in range(n + 1)]
	for sub_len in range(1, n + 1):
		for left in range(0, n - sub_len + 1):
			right = left + sub_len - 1
			if sub_len == 1:
				dp[left][right] = 1
			elif sub_len == 2:
				if s[left] == s[right]:
					dp[left][right] = 2
			elif s[left] == s[right] and dp[left + 1][right - 1] > 0:
				dp[left][right] = dp[left][left + sub_len // 2 - 1] + 1
			count[dp[left][right]] += 1
	for i in range(n - 1, 0, -1):
		count[i] += count[i + 1]
	for i in range(1, n + 1):
		print(count[i], end=' ')
	print()
main()


s = input()
n = len(s)
max_palin = [[0 for i in range(n + 1)] for j in range(n + 1)]
count = [0 for i in range(n + 1)]
for sub_len in range(1, n + 1):
	for left in range(0, n - sub_len + 1):
		right = left + sub_len - 1
		if sub_len == 1:
			max_palin[left][right] = 1
		elif sub_len == 2:
			if s[left] == s[right]:
				max_palin[left][right] = 2
			else:
				max_palin[left][right] = 0
		elif s[left] == s[right] and max_palin[left + 1][right - 1] > 0:
			mid = (left + right) // 2
			if sub_len % 2 == 0:
				max_palin[left][right] = max_palin[left][mid] + 1
			else:
				max_palin[left][right] = max_palin[left][mid - 1] + 1
		count[max_palin[left][right]] += 1
for i in range(n - 1, 0, -1):
	count[i] += count[i + 1]
for i in range(1, n + 1):
	print(count[i], end=' ')
print()


def PanlidromicCharacteristics(string):
	n = len(string)
	res = [[0 for i in range(n)] for j in range(n)]
	count = [0 for i in range(n + 1)]
	for length in range(1, n + 1):
		for i in range(n - length + 1):
			j = i + length - 1
			if length == 1:
				res[i][j] = 1
			elif length == 2 and string[i] == string[j]:
				res[i][j] = 2
			elif string[i] == string[j] and res[i + 1][j - 1] > 0:
				res[i][j] = res[i][i + length // 2 - 1] + 1
			count[res[i][j]] += 1
	for i in range(len(count) - 1, 0, -1):
		count[i - 1] += count[i]
	for i in range(1, len(count)):
		print(count[i], end=' ')
	return
string = input()
PanlidromicCharacteristics(string)


def main():
	s = input()
	n = len(s)
	isPalindrome = [[False for i in range(n + 1)] for i in range(n + 1)]
	for i in range(n):
		isPalindrome[i][i] = True
	for i in range(n - 1, -1, -1):
		for j in range(i + 1, n):
			if s[i] == s[j] and (i + 1 == j or isPalindrome[i + 1][j - 1] == True):
				isPalindrome[i][j] = True
	degreePalindrome = [[0 for i in range(n)] for i in range(n)]
	res = [0] * (n + 1)
	for i in range(n):
		for j in range(i, n):
			if i == j:
				degreePalindrome[i][j] = 1
			elif isPalindrome[i][j]:
				mid = (i + j - 1) // 2
				degreePalindrome[i][j] = degreePalindrome[i][mid] + 1
			res[degreePalindrome[i][j]] += 1
	for i in range(n - 2, 0, -1):
		res[i] += res[i + 1]
	print(*res[1:])
main()


s = input()
size = len(s)
dp = [[0 for l in range(size)] for li in range(size)]
ans = [0] * (size + 1)
for i in range(1, size + 1):
	if i == 1:
		for j in range(0, size):
			dp[j][j] = 1
			ans[1] += 1
	elif i == 2:
		for j in range(0, size - 1):
			if s[j + 1] == s[j]:
				dp[j][j + 1] = 2
				ans[1] += 1
				ans[2] += 1
			else:
				dp[j][j + 1] = 0
	else:
		for j in range(0, size - i + 1):
			if s[j] != s[j + i - 1] or dp[j + 1][j + i - 2] == 0:
				dp[j][j + i - 1] = 0
			else:
				dp[j][j + i - 1] = dp[j][int((j + j + i - 2) / 2)] + 1
				for p in range(1, dp[j][j + i - 1] + 1):
					ans[p] += 1
for i in range(1, size):
	print(ans[i], end='')
	print(' ', end='')
print(ans[size])


class HString:

	def __init__(self, string, base=257, modulo=1000000007):
		(self.__base, self.__modulo) = (base, modulo)
		(self.__prefix_hash, self.__base_pow, self.__size) = ([], [1], 0)
		self += string

	def __add__(self, string):
		for ch in string:
			self.__base_pow.append(self.__base_pow[-1] * self.__base % self.__modulo)
			if self.__size == 0:
				self.__prefix_hash.append(ord(ch))
			else:
				self.__prefix_hash.append((self.__prefix_hash[-1] * self.__base + ord(ch)) % self.__modulo)
			self.__size += 1
		return self

	def size(self):
		return self.__size

	def getModulo(self):
		return self.__modulo

	def getHashValue(self, st, en):
		value = self.__prefix_hash[en]
		if st > 0:
			value -= self.__prefix_hash[st - 1] * self.__base_pow[en - st + 1] % self.__modulo
			if value < 0:
				value += self.__modulo
		return value

def palindromic_characteristics(s):
	(n, org, rev) = (len(s), HString(s), HString(s[::-1]))
	palindrome_level = [[0 for _ in range(n)] for _ in range(n)]
	palindrome_level_count = [0 for _ in range(n + 1)]
	(i, j) = (0, 0)
	while i < n:
		j = i
		while j < n:
			if org.getHashValue(i, j) == rev.getHashValue(n - 1 - j, n - 1 - i):
				mid = (i + j) // 2 + (i + j) % 2
				if i > mid - 1:
					palindrome_level[i][j] = 1
				else:
					palindrome_level[i][j] = palindrome_level[i][mid - 1] + 1
				palindrome_level_count[palindrome_level[i][j]] += 1
			j += 1
		i += 1
	for i in range(n - 1, 0, -1):
		palindrome_level_count[i] += palindrome_level_count[i + 1]
	return palindrome_level_count[1:]
s = input()
print(' '.join(map(str, palindromic_characteristics(s))))


P = 311
MOD1 = int(1000000000.0) + 7
MOD2 = int(1000000000.0) + 9

def main():
	s = input()
	n = len(s)
	power_1 = [0 for i in range(n + 1)]
	power_2 = [0 for i in range(n + 1)]
	mod_inv_1 = [0 for i in range(n + 1)]
	mod_inv_2 = [0 for i in range(n + 1)]
	power_1[0] = 1
	power_2[0] = 1
	mod_inv_1[0] = 1
	mod_inv_2[0] = 1
	for i in range(1, n + 1):
		power_1[i] = power_1[i - 1] * P % MOD1
		power_2[i] = power_2[i - 1] * P % MOD1
		mod_inv_1[i] = bin_exp(power_1[i], MOD1 - 2, MOD1)
		mod_inv_2[i] = bin_exp(power_2[i], MOD2 - 2, MOD2)
	hash_1 = 0
	hash_2 = 0
	forward_hash_1 = [0 for i in range(n + 1)]
	forward_hash_2 = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		hash_1 += ord(s[i - 1]) * power_1[i]
		hash_2 += ord(s[i - 1]) * power_2[i]
		hash_1 %= MOD1
		hash_2 %= MOD2
		forward_hash_1[i] = hash_1
		forward_hash_2[i] = hash_2
	hash_1 = 0
	hash_2 = 0
	backward_hash_1 = [0 for i in range(n + 1)]
	backward_hash_2 = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		hash_1 += ord(s[n - i]) * power_1[i]
		hash_2 += ord(s[n - i]) * power_2[i]
		hash_1 %= MOD1
		hash_2 %= MOD2
		backward_hash_1[i] = hash_1
		backward_hash_2[i] = hash_2
	dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
	count = [0 for i in range(n + 1)]
	for sub_len in range(1, n + 1):
		for left in range(0, n - sub_len + 1):
			right = left + sub_len - 1
			if sub_len == 1:
				dp[left][right] = 1
			elif sub_len == 2:
				if s[left] == s[right]:
					dp[left][right] = 2
			elif s[left] == s[right] and dp[left + 1][right - 1] > 0:
				dp[left][right] = dp[left][left + sub_len // 2 - 1] + 1
			count[dp[left][right]] += 1
	for i in range(n - 1, 0, -1):
		count[i] += count[i + 1]
	for i in range(1, n + 1):
		print(count[i], end=' ')
	print()

def bin_exp(a, x, mod):
	res = 1
	while x > 0:
		if x & 1:
			res *= a
			res %= mod
		a *= a
		a %= mod
		x >>= 1
	return res

def get_forward_hash(forward_hash, mod_inv, left, right, mod):
	return (forward_hash[right + 1] - forward_hash[left] + mod) * mod_inv[left] % mod

def get_backward_hash(backward_hash, mod_inv, n, left, right):
	r_left = n - left - 1
	r_right = n - right - 1
	return (backward_hash[r_left + 1] - backward_hash[r_right] + mod) * mod_inv[r_right] % mod

def __starting_point():
	main()
__starting_point()


s = input()
n = len(s)
dp = [[0 for i in range(n - le + 1)] for le in range(n + 1)]
ans = [0 for i in range(n + 1)]
for le in range(1, n + 1):
	for l in range(0, n - le + 1):
		r = l + le
		if s[l] != s[r - 1]:
			continue
		if le == 1:
			dp[1][l] = 1
			ans[1] += 1
		elif le == 2:
			ans[2] += 1
			dp[2][l] = 2
		elif dp[le - 2][l + 1]:
			v = 1
			m = (l + r) // 2
			st = m + 1 if le & 1 else m
			le2 = m - l
			q = dp[le2][l]
			if q:
				v = q + 1
			ans[v] += 1
			dp[le][l] = v
for i in range(n - 1, 0, -1):
	ans[i] += ans[i + 1]
print(*ans[1:])


s = input().strip()
n = len(s)
pl = [0] * (n + 1)
dp = [[0] * n for i in range(n)]
for i in range(n):
	for j in range(n - i):
		l = j + i
		if i == 0:
			dp[j][l] = 1
			pl[1] += 1
		elif i == 1:
			if s[j] == s[l]:
				dp[j][l] = 2
				pl[2] += 1
		elif s[j] == s[l] and dp[j + 1][l - 1] > 0:
			if (i + 1) % 2 == 0:
				mid = int((i + 1) / 2) - 1
				dp[j][l] = dp[j][j + mid] + 1
				pl[dp[j][l]] += 1
			else:
				mid = int((i + 1) / 2) - 1
				dp[j][l] = dp[j][j + mid] + 1
				pl[dp[j][l]] += 1
ans = ''
for i in range(n - 1, -1, -1):
	pl[i] += pl[i + 1]
for i in range(1, n + 1):
	ans = ans + str(pl[i]) + ' '
print(ans)


s = input()
dp = [[0] * 5005 for _ in range(5005)]
n = len(s)
ans = [0 for _ in range(5005)]
for length in range(1, n + 1):
	for l in range(n - length + 1):
		r = l + length
		if length == 1:
			dp[l][r] = 1
			continue
		elif length == 2:
			dp[l][r] = 2 if s[l] == s[r - 1] else 0
			continue
		if s[l] != s[r - 1] or dp[l + 1][r - 1] == 0:
			continue
		dp[l][r] = 1
		m = (l + r) // 2
		if length & 1:
			if dp[l][m] and dp[m + 1][r]:
				dp[l][r] = dp[l][m] + 1
		elif dp[l][m] and dp[m][r]:
			dp[l][r] = dp[l][m] + 1
for length in range(1, n + 1):
	for l in range(n - length + 1):
		ans[dp[l][l + length]] += 1
for i in range(n - 1, 0, -1):
	ans[i] += ans[i + 1]
for i in range(1, n + 1):
	print(ans[i], end=' ')
print()


def palindromic_characteristics(s):
	n = len(s)
	palindrome_level = [[0 for _ in range(n)] for _ in range(n)]
	palindrome_level_count = [0 for _ in range(n + 1)]
	for i in range(n):
		j = i
		while i >= 0 and j < n and (s[i] == s[j]):
			palindrome_level[i][j] = 1
			(i, j) = (i - 1, j + 1)
	for i in range(n - 1):
		j = i + 1
		while i >= 0 and j < n and (s[i] == s[j]):
			palindrome_level[i][j] = 1
			(i, j) = (i - 1, j + 1)
	for i in range(n):
		for j in range(i, n):
			if palindrome_level[i][j] > 0:
				mid = (i + j) // 2 + (i + j) % 2
				if i <= mid - 1:
					palindrome_level[i][j] = palindrome_level[i][mid - 1] + 1
				palindrome_level_count[palindrome_level[i][j]] += 1
	for i in range(n - 1, 0, -1):
		palindrome_level_count[i] += palindrome_level_count[i + 1]
	return palindrome_level_count[1:]
s = input()
print(' '.join(map(str, palindromic_characteristics(s))))