Palindrome tree

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Palindrome tree" – news · newspapers · books · scholar · JSTOR (February 2022) (Learn how and when to remove this message)

In

Like most trees, a palindrome tree consists of

Since a palindrome tree follows an online construction, it maintains a pointer to the last palindrome added to the tree. 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. Otherwise, a new vertex is added with a link from the suffix to the new vertex, and a suffix link for the new vertex is added. 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.

# S -> Input String
# x -> position in the string of the character being added
def add(x: int) -> bool:
    """Add character to the palindrome tree."""
    while True:
        if x - 1 - current.length >= 0 and S[x - 1 - current.length] == S[x]:
            break
        current = current.suffix

    if current.add[S[x]] is not None:
        return False

    suffix = current
    current = Palindrome_Vertex()
    current.length = suffix.length + 2
    suffix.add[S[x]] = current

    if current.length == 1:
        current.suffix = root
        return True

    while True:
        suffix = suffix.suffix
        if x - 1 - suffix.length >= 0 and S[x - 1 - suffix.length] == S[x]:
            current.suffix = suffix.add[S[x]]
            return True

Finding palindromes that are common to multiple strings or unique to a single string can be done with ${\displaystyle O(n*i)}$ additional space where ${\displaystyle i}$ is the number of strings being compared. This is accomplished by adding an array of length ${\displaystyle i}$ to each vertex, and setting the flag to 1 at index ${\displaystyle i}$ if that vertex was reached when adding string ${\displaystyle i}$. The only other modification needed is to reset the current pointer to the root at the end of each string. By joining trees in such a manner the following problems can be solved:

• Number of palindromes common to all strings
• Number of unique palindromes in a string
• Longest palindrome common to all strings
• The number of palindromes that occur more often in one string than others

Constructing a palindrome tree takes ${\displaystyle O(n\log {\sigma })}$ time, where ${\displaystyle n}$ is the length of the string and ${\displaystyle \sigma }$ is the size of the alphabet. With ${\displaystyle n}$ calls to add(x), each call takes ${\displaystyle O(\log {\sigma })}$

${\displaystyle O(\log {\sigma })}$

A palindrome tree takes ${\displaystyle O(n)}$ space: At most ${\displaystyle n+2}$ vertices to store the sub-palindromes and two roots, ${\displaystyle n}$ edges, linking the vertices and ${\displaystyle n+2}$ suffix edges.

If instead of storing only the add edges that exist for each palindrome an array of length ${\displaystyle \sigma }$ edges is stored, finding the correct edge can be done in constant time reducing construction time to ${\displaystyle O(n+p*\sigma )}$ while increasing space to ${\displaystyle O(p*\sigma )}$, where ${\displaystyle p}$ is the number of palindromes.