Palindrome tree

In computer science a palindrome tree, also called an EerTree,[1] is a type of search tree, that allows for fast access to all palindromes contained in a string.

They can be used to solve the longest palindromic substring, the k-factorization problem[2] (can a given string be divided into exactly k palindromes), palindromic length of a string[3] (what is the minimum number of palindromes needed to construct the string), and finding and counting all distinct sub-palindromes.

Palindrome trees do this in an online manner, that is it does not require the entire string at the start and can be added to character by character.

Each vertex in the tree represents a palindrome (e.g. 'tacocat') but only stores the length of the palindrome, and each edge represents either a character or a suffix.

The character edges represent that when the character is appended to both ends of the palindrome represented by the source vertex, the palindrome in the destination vertex is created (e.g. an edge labeled 't' would connect the source vertex 'acoca' to the destination vertex 'tacocat').

The two roots represent palindromes of length −1, and 0.

That is, if the character 'a' is appended to both roots the tree will produce 'a' and 'aa' respectively.

To add the next character to the palindrome tree, add(x) first checks if the first character before the palindrome matches the character being added, if it does not, the suffix links are followed until a palindrome can be added to the tree.

Once a palindrome has been found, if it already existed in the tree, there is no work to do.

If the length of the new palindrome is 1, the suffix link points to the root of the palindrome tree that represents a length of −1.

This is accomplished by adding an array of length

to each vertex, and setting the flag to 1 at index

The only other modification needed is to reset the current pointer to the root at the end of each string.

This is a result of each call to add(x) increases the depth of the current vertex (the last palindrome in the tree) by at most one, and searching all possible character edges of a vertex takes

By assigning the cost of moving up and down the tree to each call to add(x), the cost of moving up the tree more than once is 'paid for' by an equal number of calls to add(x) when moving up the tree did not occur.

If instead of storing only the add edges that exist for each palindrome an array of length

edges is stored, finding the correct edge can be done in constant time reducing construction time to