StringsString Algorithms

Suffix Tree (Compressed Trie of Suffixes)

A compressed trie of all suffixes of a string; answers substring search in O(m), longest repeat and distinct-substring counts directly from its structure.

Learn Suffix Tree →

String — Letters only, 2 to 9 characters — the terminal "$" is appended for you

Suffixes inserted

empty

1/20The text is "banana$": a terminal "$" is appended so that no suffix is a prefix of another, which guarantees every one of the 7 suffixes ends at its own leaf instead of halfway down an edge.

Node being matched againstMatched so farEdge just splitNew leaf (suffix start index)

PseudocodeLearn Suffix Tree →

1build(s + "$"):
2  for i in 0 .. len(s):            # every suffix, longest first
3    rest = s[i:] ; node = root
4    while rest is not empty:
5      if no child edge starts with rest[0]: attach leaf(rest, index = i)
6      k = length of the common prefix of that edge and rest
7      if k == len(edge): node = child ; rest = rest[k:]      # walk through
8      else: split the edge after k characters                # edge compression
9            attach leaf(rest[k:], index = i) under the new node

Variables

nodes1

leaves1

textbanana$

suffixes7

Complexity

best O(n)

avg O(n)

worst O(n)

space O(n · σ)

Speed