Suffix Trie - Summary

https://stackoverflow.com/questions/13893950/suffix-tree-and-tries-what-is-the-difference

A suffix tree can be viewed as a data structure built on top of a trie where, instead of just adding the string itself into the trie, you would also add every possible suffix of that string. As an example, if you wanted to index the string banana in a suffix tree, you would build a trie with the following strings:

banana
anana
nana
ana
na
a

Once that's done you can search for any n-gram and see if it is present in your indexed string. In other words, the n-gram search is a prefix search of all possible suffixes of your string.

This is the simplest and slowest way to build a suffix tree. It turns out that there are many fancier variants on this data structure that improve on either or both space and build time.

https://www.quora.com/When-to-use-suffix-Tree-and-when-to-use-Trie-is-it-good-to-use-suffix-tree-with-large-text-instead-of-tree

Suffix tree is used when you want to search a substring inside a sentence.
But trie is used when. You want to do a search for keyword among group of words (dictionary)

https://www.cs.helsinki.fi/u/tpkarkka/opetus/13s/spa/lecture10.pdf
https://www.hackerearth.com/practice/notes/trie-suffix-tree-suffix-array/

There is a famous algorithm by Ukkonen for building suffix tree for s in linear time in terms of the length of s. However, because it may look quite complicated at first sight, many people are discouraged to learn how it works. Fortunately, there is a great, I mean an excellent, description of Ukkonen's algorithm given on StackOverflow. Please refer to it for better understanding what a suffix tree is and how to build it in linear time.

Suffix trees can solve many complicated problems, because it contain so many information about the string itself. Fo example, in order to know how many times a pattern P occurs in s, it is sufficient to find P in T and return the size of a subtree corresponding to its node. Another well known application is finding the number of distinct substrings of s, and it can be solved easily with suffix tree, while the problem looks very complicated at first sight.

If you want to know more about when to use a suffix tree, you should read this paper about the applications of suffix trees.

TODO: https://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english/9513423#9513423