Palindromic characteristics (Codeforces 835D)
Tags: Others, hashing

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.

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.

Sample Inputs:
abba

abacaba

Sample Outputs:
6 1 0 0

12 4 1 0 0 0 0

Solution (Python):
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))))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * n + v
s = list(input().rstrip())
n = len(s)
m = n * n
dp = [-1] * m
for i in range(n):
    dp[f(i, i)] = 0
    (l, r) = (i - 1, i + 1)
    while 0 <= l and r < n and (s[l] == s[r]):
        dp[f(l, r)] = 0
        l -= 1
        r += 1
for i in range(n - 1):
    (l, r) = (i, i + 1)
    while 0 <= l and r < n and (s[l] == s[r]):
        dp[f(l, r)] = 0
        l -= 1
        r += 1
for i in range(1, n):
    d = (i - 1) // 2
    for l in range(n - i):
        r = l + i
        u = f(l, r)
        if min(dp[u], dp[f(l, l + d)], dp[f(r - d, r)]) ^ -1:
            dp[u] = dp[f(l, l + d)] + 1
ans = [0] * n
for i in dp:
    if i ^ -1:
        ans[i] += 1
for i in range(n - 2, -1, -1):
    ans[i] += ans[i + 1]
sys.stdout.write(' '.join(map(str, ans)))

Solution (Python):
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:])