An O(n) Solution to Codeforces 835D
Разница между en1 и en2, 0 символ(ов) изменены
**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]**

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский suncongbo 2019-06-21 06:38:03 4 Tiny change: 'as the max $k$ that ' -> 'as the maximum $k$ that '
en2 Английский suncongbo 2019-06-21 06:35:12 0 (published)
en1 Английский suncongbo 2019-06-21 06:34:30 2382 Initial revision (saved to drafts)