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...

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

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

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.