Suffix tree and suffix array visualizer

Type a string (a $ is added to the end) and a pattern to search for. The tree shows every suffix as a path from the root to a leaf, with edges labelled by the characters they spell; each leaf is numbered with the position where its suffix starts. The table lists the suffixes in sorted order, which is the suffix array, with the LCP array beside it.

• The search path is highlighted in the tree, and the block of matching suffixes in the table.
• Switch positions to start at 1 if your course numbers characters from 1. Copy answer gives the arrays, the search steps and the counts as text.

Every substring of a text is a prefix of one of its suffixes: "nan" is the start of "nana". A suffix tree stores all the suffixes in one compressed trie, so finding any substring means walking down from the root, one character at a time. A unique end marker, $, keeps any suffix from being the prefix of another, so each suffix ends at its own leaf.

Chains of single-child nodes are merged into edges labelled with several characters, which keeps the size linear: a string of length n has n + 1 leaves (one per suffix, counting $) and fewer internal nodes than that. For banana$ the tree has 7 leaves, 3 internal nodes and the root.

A suffix array lists the starting positions of all suffixes in alphabetical order of the suffixes, with $ sorting first. It holds the same information as the leaves of the suffix tree read left to right, in a single array of integers. For banana$:

The LCP array records, for each suffix in sorted order, the length of the longest common prefix it shares with the one before it. Neighbours in sorted order share the longest prefixes, so the LCP array captures all the repetition in the text. Kasai's algorithm builds it in O(n) from the suffix array, using the fact that moving from one suffix to the next in the text loses at most one character of common prefix.

Its maximum is the length of the longest repeated substring: "ana" in banana and "issi" in mississippi. Subtracting the LCP values from the total number of substrings counts the distinct substrings, because each LCP entry is a set of prefixes already counted for the previous suffix: banana has 15, mississippi 53.

In the suffix tree, a search walks down from the root matching the pattern against edge labels. If it runs out of pattern, every leaf below the stopping point is an occurrence: "ana" in banana stops on the edge into a node with two leaves, positions 1 and 3. If a character fails to match, the pattern does not occur. The walk takes O(m) steps for a pattern of length m, however long the text.

In the suffix array, all suffixes that start with the pattern sit together in one block, so two binary searches find its first and last rows in O(m log n) character comparisons. Searching mississippi for "ssi" finds positions 2 and 5 in 5 probes. With the LCP array, the search can avoid re-comparing characters it has already matched.

• Longest repeated substring: the deepest internal node of the tree, or the largest LCP value.
• Number of distinct substrings: the total length of all edge labels, or n(n + 1)/2 minus the sum of the LCP array.
• Longest common substring of two strings: build the structure for both joined by a separator and find the deepest node with suffixes from each.
• Counting occurrences: the number of leaves below a node, or the size of the block in the suffix array.

Inserting each suffix into a trie one at a time, as this page does, takes O(n²) time, which is fine for short strings. Esko Ukkonen's 1995 algorithm builds the suffix tree online, one character at a time, in O(n) time for a fixed alphabet, using suffix links to jump between related nodes. Suffix arrays can be built by sorting with prefix doubling in O(n log n), or in O(n) with algorithms such as SA-IS. Suffix arrays need several times less memory than suffix trees, which is why Manber and Myers proposed them.