Ukkonen's Algorithm

Esko Ukkonen, 1995

Ukkonen (1995) constructs a suffix tree in O(n) time by processing characters left to right. Each phase extends the implicit suffix tree—this exhibit inserts suffixes one by one, showing leaf creation and edge splitting as the tree grows.