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

Failure-linked tries: find overlapping alert terms in one scan

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

A failure-linked trie indexes several fixed search terms so one pass through a message can report all of them. Each trie node stores character edges, a fallback state for the longest suffix that is also a term prefix, and term IDs that end at that state. A breadth-first build assigns fallbacks from shorter prefixes outward. During scanning, a missing edge follows failures until another edge or the root applies. Output lists inherited from the failure state preserve suffix matches and overlapping terms; skipping that inheritance silently loses valid hits. This implementation rejects empty and duplicate terms, keeps matching case-sensitive, and reports offsets in Python Unicode code points.

Operational case

The alert index contains heat, eat, and seal. Scanning overheat seal heat reports heat beginning at offset 4 and eat at 5, seal at 9, and the two overlapping heat/eat matches again near the end. One input character can complete several indexed terms. The resulting pairs are ordered by ending position and then by the terms stored on that state; they are not necessarily sorted by starting offset. The term set is immutable after construction, which matters because adding a term would require rebuilding failure links and inherited output lists.

Working Python program

python
"""Failure-linked trie for simultaneous, overlapping alert-term matches."""

from collections import deque


class AlertNode:
    def __init__(self):
        self.edges = {}
        self.failure = 0
        self.matches = []


class AlertIndex:
    def __init__(self, alert_terms):
        self.terms = tuple(alert_terms)
        if not self.terms or any(not term for term in self.terms):
            raise ValueError("alert terms must be nonempty")
        if len(set(self.terms)) != len(self.terms):
            raise ValueError("duplicate alert term")
        self.nodes = [AlertNode()]
        for term_number, term in enumerate(self.terms):
            position = 0
            for character in term:
                if character not in self.nodes[position].edges:
                    self.nodes[position].edges[character] = len(self.nodes)
                    self.nodes.append(AlertNode())
                position = self.nodes[position].edges[character]
            self.nodes[position].matches.append(term_number)

        pending = deque(self.nodes[0].edges.values())
        while pending:
            position = pending.popleft()
            for character, child in self.nodes[position].edges.items():
                fallback = self.nodes[position].failure
                while fallback and character not in self.nodes[fallback].edges:
                    fallback = self.nodes[fallback].failure
                self.nodes[child].failure = self.nodes[fallback].edges.get(character, 0)
                self.nodes[child].matches.extend(self.nodes[self.nodes[child].failure].matches)
                pending.append(child)

    def scan(self, message):
        position = 0
        found = []
        for offset, character in enumerate(message):
            while position and character not in self.nodes[position].edges:
                position = self.nodes[position].failure
            position = self.nodes[position].edges.get(character, 0)
            for term_number in self.nodes[position].matches:
                term = self.terms[term_number]
                found.append((offset - len(term) + 1, term))
        return found


alerts = AlertIndex(("heat", "eat", "seal"))
print(alerts.scan("overheat seal heat"))

Output

Output
[(4, 'heat'), (5, 'eat'), (9, 'seal'), (14, 'heat'), (15, 'eat')]

Time, space, and tradeoff

Let M be the total term length, H the longest term, N the message length, and Z the number of reported matches. This sparse-edge builder uses O(M) trie nodes but may walk up to H failure links while assigning an edge, so a conservative construction bound is O(MH + R) time, where R counts inherited output references. Stored output lists can also reach O(M + R) space. Once built, scanning takes O(N + Z) amortized time: each fallback reduces the active prefix depth, while each character can increase it by at most one. Holding the returned match list takes O(Z) space. Large term sets with many suffix relationships can make output storage substantial; consider streaming matches when result volume is high.

Common Mistakes

  • Do not discard matches inherited through a failure link.
  • Do not assume one character can end only one term.
  • Do not call code-point offsets UTF-8 byte positions.
  • Do not mutate the term set without rebuilding the failure graph.

Connected lessons

Apply this structure in the incident search project, then test the index decisions quiz.

Suffix automata: index substrings as text arrives adds a related operation contract.

Positional postings: find exact token phrases adds a related indexing contract.

data structures
range-query-structures
Storage details