Define the set of suffix strings for a string S to be S, S without its first character,
S without its first two characters, and so on. For example, the complete
set of suffix strings for “HELLO” would be

A suffix tree is a PAT trie that contains all of the suffix strings for a given
string, and associates each suffix with the complete string. The advantage
of a suffix tree is that it allows a search for strings using “wildcards.” For
example, the search key “TH*” means to find all strings with “TH” as the
first two characters. This can easily be done with a regular trie. Searching
for “*TH” is not efficient in a regular trie, but it is efficient in a suffix tree.
Implement the suffix tree for a dictionary of words or phrases, with support
for wildcard search.

Transcribed Image Text:

{HELLO, ELLO, LLO, LO, O}.