**Summary: This blog gives a solution to [problem:835D] 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: [submission:55849948]**
↵
#### 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: [submission:55849948]**
