Summary: This blog gives a solution to 835D - Palindromic characteristics which uses Palindromic Tree (also named Palindromic Automaton) and works in $$$O(n)$$$ time.

Solution

(we define "palindromic level" of string $$$s$$$ as the max $$$k$$$ that satisfies $$$s$$$ is $$$k$$$-palindromic)

Consider the $$$O(n^2)$$$ DP solution: let $$$dp[l][r]$$$ be the palindromic level of substring $$$[l,r]$$$. It is obvious that $$$dp[l][r]\ne 0$$$ only if substring $$$[l,r]$$$ is a palindrome. So only the palindromic substrings are useful DP states.

There is an important property of palindromes: there are only $$$O(n)$$$ different palindromic substrings in a string with length $$$n$$$, where the same string appearing in different positions are considered same. This is because if there are two palindromes with lengths $$$l_1$$$ and $$$l_2$$$ ending in a position $$$i$$$ ($$$l_2<l_1\le i$$$), then the substring $$$[i-l_2+1,i-l_2+l_1]$$$ is the same as $$$[i-l_1+1,i]$$$, for they are in the symmetrical positions of the palindrome $$$[i-l_2+1,i]$$$. According to this we can build a Palindromic Automaton and each vertex on the Palindromic Tree corresponds with a unique palindromic substring. Then we can easily express a palindromic substring with the corresponding vertex on the Palindromic Automaton. Let $$$dp[x]$$$ be the palindromic level of vertex $$$x$$$.

The transferring method is obvious. If there exists vertex $$$y$$$ satisfying $$$len[y]=[\frac{len[x]}{2}]$$$ ($$$len[x]$$$ denotes the length of corresponding substring of vertex $$$x$$$) then $$$dp[x]=dp[y]+1$$$. Otherwise, $$$dp[x]=1$$$.

Now let's see how to determine for each $$$x$$$ whether there exists a vertex $$$y$$$. Let $$$bd[x]$$$ be the longest palindromic suffix of $$$x$$$ which length doesn't exceed half of $$$len[x]$$$. When we create a new vertex $$$x$$$, we find vertex $$$p$$$, the substring left by cutting out the first and the last characters of string $$$x$$$. We iterate from $$$v=bd[p]$$$, each time we replace $$$v$$$ with $$$fail[v]$$$, until its corresponding son can be valid $$$bd[x]$$$. See my code to learn more details about this process.

Finally, the problem asks for substrings which differs in position, but we answered substrings which differs in contents. So we have to calculate $$$sz[x]$$$, the size of subtree for each $$$x$$$. $$$sz[x]$$$ is also the number of appearances of substring $$$x$$$.

It's obvious that this solution works in $$$O(n)$$$ time.

My AC code is here: 55849948