Learning notes on Palindrome Tree

Basic things this structure can do
  1. the number of distinct palindrome substring in a string (which turns out to be the number of extra states, which is linear)
  2. the number of times each palindrome appears
  3. The number of palindromes (or sum of the corresponding properties) that ends in a certain location.
Properties
  1. The size of the tree is $O(n)$. This is a result of the fact that at most one new distinct palindrome can be added when we add a new character. (Otherwise, choose the longest of them, $s_{longest}$, and the shorter one will definitely appear if we flip it from the middle point of $s_{longest}$.)
  2. Each fail pointer is pointing to a smaller index. So when we want to do tree DP, we can just use the index as the topological order.
Other tricks:

Adding characters from both sides: HDU 5421
To do such thing, we can keep a extra pointer at the begining of the string. Both pointer will be the longest palindrome prefix/suffix. The operations will be symmetric, and, additionally, when the new distinct palindrome we get is the new whole string, we need to update both pointer to keep the property of the pointers.

Series Link

To be continued…

Leave a Reply

Your email address will not be published. Required fields are marked *