#6 Implement efficient suffix tree and algorithms with it

[Victor Anyakin]

There is already a very primitive and naїve Trie implementation for the Aho-Corasick algorithm.

Implement efficient Suffix tree data structure (see here) and algorithms on strings utilizing this data structure.

[Victor Anyakin]

Another description of the Ukkonen's algorithm and Suffix tree: allisons.org: Suffix Trees

[Victor Anyakin]

Yet another useful resource with program sources:

• Liu Xinyu, Suffix Tree with Functional and imperative implementation

[Victor Anyakin]

Suffix tree construction should be refined to have a better node children data structure (either a hash map, or a tree map).

Also McCreight construction algorithm implementation.

Suffix tree applications:

• Exact string matching
• Longest common substring of two strings
• DNA Contamination problem