UKKONEN'S TREE not the first suffix tree - the first online one
A suffix tree indexes every suffix of a string in one structure, so substring search, longest-repeat, and matching become a walk from the root — in time proportional to the query, not the text. Ukkonen’s 1995 construction builds it left-to-right, online, in linear time, using an “active point” and suffix links. It is famous for being correct, fast, and very hard to understand.
THE TECHNIQUE all suffixes, shared by prefix
Every suffix of the string is a path from the root; shared prefixes share edges (each labelled by a substring, stored as two indices). Build it once and every substring question is a walk. Ukkonen adds it one character at a time, keeping an active point and suffix links to reach amortised O(n). Below: the distinct-substring count and tree shape for a word. live demo
HISTORY & CREDIT first is Weiner; online is Ukkonen
“Ukkonen invented the linear-time suffix tree” — Weiner did, in 19951973; Ukkonen’s first is the online version. cited
1973 · Peter Weiner builds the first linear-time suffix structure (he called it a “bi-tree,” built right-to-left) — Knuth reportedly called it “the algorithm of the year.” 1976 · Edward McCreight gives the name “suffix tree,” a simpler left-to-right build, and suffix links — not Ukkonen’s invention. 1995 · Esko Ukkonen — the online (prefix-at-a-time) linear-time construction with the active point; the version people actually teach and implement. the payoff · a string can have up to Θ(n²) distinct substrings (banana: 15), yet the suffix tree represents them all with only O(n) nodes — linear space, not a linear count.
Suffix arrays (dart-adjacent) later gave the same power in less memory; the tree is still the clearest picture. Weiner 1973 / Ukkonen 1995
RECOMMEND FOR I-13 the active point runs; the tree is the wall
The active-point index arithmetic is array-native; the counting is exact:
Recommend: all the bookkeeping runs — active-node id, active-edge index, active-length, the remainder counter, the global end, and every edge label as a (start, end) pair of integer indices into the string are f64-representable and array-native (verified banana → 15 distinct). The wall is the suffix tree itself: nodes with child pointers and suffix links — PS-015, the pointer wall, shared with AVL (072), red-black (073), the trie (074), the k-d tree (078). Note: the node-arena encoding (children/suffix-link as parallel index arrays) runs today; a first-class linked value is the honest add.