Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Ukkonen's algorithm
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, Ukkonen's algorithm is a linear-time, <a href="/facts/Online_algorithm/64TsU7Yz">online algorithm</a> for constructing <a href="/facts/Suffix_tree/pdQdCxbe">suffix trees</a>, proposed by <a href="/facts/Esko_Ukkonen/g3Y8062g">Esko Ukkonen</a> in 1995. The algorithm begins with an implicit suffix tree containing the first character of the string. Then it steps through the string, adding successive characters until the tree is complete. This order addition of characters gives Ukkonen's algorithm its "on-line" property. The original algorithm presented by Peter Weiner proceeded backward from the last character to the first one from the shortest to the longest suffix. A simpler algorithm was found by <a href="/facts/Edward_M._McCreight/2rlaFExR">Edward M. McCreight</a>, going from the longest to the shortest suffix. </p>