AlgoVerse

Suffix tree

Put every suffix of a string into one compressed tree whose edges are pieces of the text; afterwards any pattern can be found in O(pattern length).

A suffix tree is the trie of all suffixes of a string, with its non-branching paths compressed: each edge is a piece of the text. With the end marker $ no suffix is a prefix of another, and each suffix gets its own leaf.

Read the full explanation ↓
Input:
S="banana"PDF export

banana$; the tree has 7 leaves (one per suffix), and the edges “a”, “na” and “ana” are shared.

  1. def suffix_tree(S):
  2. S = S + "$" # an end marker, so no suffix is a prefix of another and each ends at its own leaf
  3. labels = [""] # labels[v]: the text on the edge into node v (node 0 is the root)
  4. kids = [{}] # kids[v]: first letter of an outgoing edge → child
  5. rows = [[0, "-", "", "-"]] # for the picture: node, parent, edge label, suffix number at a leaf
  6. for i in range(len(S)):
  7. rest = S[i:]
  8. v = 0
  9. while True:
  10. if rest[0] not in kids[v]:
  11. labels.append(rest)
  12. kids.append({})
  13. kids[v][rest[0]] = len(labels) - 1
  14. rows.append([len(labels) - 1, v, rest, i])
  15. break
  16. c = kids[v][rest[0]]
  17. label = labels[c]
  18. k = 0
  19. while k < len(label) and label[k] == rest[k]:
  20. k = k + 1
  21. if k == len(label):
  22. v = c
  23. rest = rest[k:]
  24. continue
  25. # The suffix leaves the edge after k letters: split the edge there.
  26. mid = len(labels)
  27. labels.append(label[:k])
  28. kids.append({label[k]: c})
  29. kids[v][rest[0]] = mid
  30. labels[c] = label[k:]
  31. rows.append([mid, v, label[:k], "-"])
  32. rows[c][1] = mid
  33. rows[c][2] = label[k:]
  34. v = mid
  35. rest = rest[k:]
  36. return len(labels)

Invariant: Every inner node has at least two children and the edges out of a node start with different letters; so each substring has exactly one path from the root.

Start

012345
banana
rest—

The table is still empty.

Local variables

S'banana'

Orange = changed in this step

Call stack

  1. suffix_tree()line 1
Step 1 of 140
Black = new_leaf · Orange = key stepnew_leaf: 0/7 · split: 0/3
    Explanation

    The idea

    A suffix tree is the trie of all suffixes of a string, with its non-branching paths compressed: each edge is a piece of the text. With the end marker $ no suffix is a prefix of another, and each suffix gets its own leaf.

    The simple construction

    Insert the suffixes one by one from the root:

    • if no edge starts with the next letter, hang the rest of the suffix on a new leaf;
    • if a whole edge label matches, go down it;
    • if the suffix leaves an edge in the middle, split the edge there and make an inner node.

    This takes O(n²); Ukkonen's method builds the same tree in O(n).

    Uses

    Finding any pattern in O(m), the longest repeated substring (the deepest inner node), the longest common substring of two strings, and more.

    What to watch in the trace

    • The table lists every node: its parent, the label of the edge into it, and, for leaves, the suffix number.