Suffix tree and suffix array

Suffix tree

It’s a variant of trie. It’s also called position tree. Idea is to represent all suffixes of the given string in the tree following trie model. For example, suffixes of string Banana – {Banana, anana, nana, ana, na, a} is represented as suffix tree in the below picture. It has leaf nodes equal to the length of the string. Every leaf node represents suffix position in the string. A path from root the leaf represent a suffix. $ is the terminal character representing the ending of a suffix.

Once constructed,suffix tree supports fast string operations such as sub-string search. It’s also used for pattern matching  and compression schemes.

Suffix array

Suffix array is about representing all suffixes of a string in an array. Instead of storing suffixes, it sorts the suffixes and store the positions.

courtesy: wikipedia

References

• On hackerearth
• On visualalgo.net