Suffix Tree

The suffix tree for a string S is a tree whose edges are labeled with strings, and such that each suffix of S corresponds to exactly one path from the tree's root to a leaf. It is thus a radix tree for the suffixes of S.

Constructing such a tree for the string S takes time and space linear in the length of S.

Applications:
1. Check if a string P of length m is a substring in O(m) time


Subsequence, Substring, Suffix, Prefix

• Subsequence is a generalization of substring, suffix and prefix. Finding the longest string which is equal to a subsequence of two or more strings is known as the longest common subsequence problem.

• Substring of a string is a prefix of a suffix of the string, and equivalently a suffix of a prefix.

Lexicographical order(Lexicographic), dictionary order, alphabetic order
one may assume that all words have the same length, by adding blank spaces at the end, and considering the blank space as a special character which comes before any other letter in the alphabet. This also allows ordering of phrases.

References:
http://en.wikipedia.org/wiki/Suffix_%28computer_science%29
http://en.wikipedia.org/wiki/Suffix_tree
http://en.wikipedia.org/wiki/Lexicographical_order