Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Palindromic trees: index distinct palindromes as text arrives

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A palindromic tree keeps one node for each distinct nonempty palindrome in the text seen so far. Two special roots represent lengths minus one and zero. An append walks suffix links from the previous longest palindromic suffix until the new code point can extend that suffix on both sides. Its transition either reuses a node or creates exactly one node; the new node's suffix link points to its longest proper palindromic suffix. This index tracks how often a node was the longest suffix at an append. A later descending-length pass propagates those counts to shorter suffixes, yielding total occurrences. It accepts Unicode code points, not grapheme clusters or normalized user-visible characters.

Operational case

An incident code stream receives abacaba one code point at a time. It contains seven distinct nonempty palindromes, and the longest has length seven. The tree creates a node only when an append introduces a palindrome not seen before; an existing transition increments its end count. The example prints a sorted list of propagated occurrence counts because node IDs describe construction history, not lexicographic text order. If a caller asks for counts before the propagation pass, an inner palindrome such as a would be undercounted. Appending after a count query is safe here because that query works on a copy of the end counters.

Working Python program

python
class PalindromicIncidentTree:
    def __init__(self):
        self.text = []
        self.nodes = [
            {"length": -1, "link": 0, "next": {}, "ends": 0},
            {"length": 0, "link": 0, "next": {}, "ends": 0},
        ]
        self.last = 1

    def _extendable(self, node_id, position, letter):
        length = self.nodes[node_id]["length"]
        return position - length - 1 >= 0 and self.text[position - length - 1] == letter

    def append(self, letter):
        if len(letter) != 1:
            raise ValueError("append exactly one code point")
        self.text.append(letter)
        position = len(self.text) - 1
        candidate = self.last
        while not self._extendable(candidate, position, letter):
            candidate = self.nodes[candidate]["link"]
        transition = self.nodes[candidate]["next"]
        if letter in transition:
            self.last = transition[letter]
            self.nodes[self.last]["ends"] += 1
            return False
        new_id = len(self.nodes)
        self.nodes.append({"length": self.nodes[candidate]["length"] + 2,
                           "link": 1, "next": {}, "ends": 1})
        transition[letter] = new_id
        if self.nodes[new_id]["length"] > 1:
            suffix = self.nodes[candidate]["link"]
            while not self._extendable(suffix, position, letter):
                suffix = self.nodes[suffix]["link"]
            self.nodes[new_id]["link"] = self.nodes[suffix]["next"][letter]
        self.last = new_id
        return True

    def distinct_count(self):
        return len(self.nodes) - 2

    def longest_length(self):
        return max((node["length"] for node in self.nodes[2:]), default=0)

    def occurrence_counts(self):
        counts = [node["ends"] for node in self.nodes]
        for node_id in sorted(range(2, len(self.nodes)),
                              key=lambda item: self.nodes[item]["length"], reverse=True):
            counts[self.nodes[node_id]["link"]] += counts[node_id]
        return {node_id: counts[node_id] for node_id in range(2, len(self.nodes))}


if __name__ == "__main__":
    index = PalindromicIncidentTree()
    for letter in "abacaba":
        index.append(letter)
    print("distinct:", index.distinct_count())
    print("longest:", index.longest_length())
    print("occurrences:", sorted(index.occurrence_counts().values()))

Output

Output
distinct: 7
longest: 7
occurrences: [1, 1, 1, 1, 2, 2, 4]

Time, space, and tradeoff

With dictionary transitions and ordinary expected constant-time lookups, processing N code points takes O(N) expected time and O(N) nodes and transitions. The example's explicit count finalization sorts nodes by palindrome length, so that report costs O(N log N) time and O(N) temporary memory. The streaming index itself never stores every occurrence as a separate node. Hash-table worst cases, Unicode normalization policy, and the cost of retaining the full input text still matter. Use a suffix array or automaton when arbitrary substring questions dominate; this index answers palindrome-specific structure questions.

Common Mistakes

  • Do not count the two special roots as nonempty palindromes.
  • Do not read raw end counters as total occurrence counts.
  • Do not treat code-point equality as grapheme-aware or normalized text matching.
  • Do not assume a transition creates a new node on every append.

Connected lessons

Compare its update and query contract with Segment tree beats: cap a range while retaining its sum, Wavelet matrices: count frequencies and find subarray quantiles, Two-stack window aggregation: keep FIFO order under a monoid, then complete the structure audit and decision quiz.

data structures
range-query-structures
Storage details