Search code examples
algorithmdata-structuressuffix-tree

Conceptually simple linear-time suffix tree constructions


In 1973 Weiner gave the first linear-time construction of suffix trees. The algorithm was simplified in 1976 by McCreight, and in 1995 by Ukkonen. Nevertheless, I find Ukkonen's algorithm relatively involved conceptually.

Has there been simplifications to Ukkonen's algorithm since 1995?


Solution

  • It's not a direct answer, however it can help you.

    Last year, while working on the subject, I ended using suffix-arrays instead of suffix-trees, and IIRC, I used the paper "An incomplex algorithm for fast suffix array construction " KB Schürmann (2007) [1] as a reference. IIRC, it's a two pass linear algorithm to build suffix-arrays.

    [1] http://scholar.google.com/scholar?q=An+incomplex+algorithm+for+fast+suffix+array+construction+&hl=en&btnG=Search&as_sdt=1%2C5&as_sdtp=on