P9282 [AGM 2023 Qualifier] Palindrome.

Define a function $f(x)$ for a string $x$ as follows: - If $x$ has length $1$, then $f(x)=1$. - If $x$ is not a palindrome, then $f(x)=0$. - If $x$ is a palindrome, let $y$ be the string consisting of the first $\frac{|x|+1}{2}$ characters of $x$. Then $f(x)=f(y)+1$. Given a string $s$ and an integer $k$, for every non-empty substring of $s$, count how many substrings have $f$ equal to each value from $1$ to $k$.

The first line contains two integers $N(1\leq N\leq 10^5)$ and $k(1\leq k\leq 30)$. The next line contains a string $s$ of length $N$, consisting only of lowercase letters.

Output the answers for each value from $1$ to $k$.

Translated by ChatGPT 5