Introduction to Suffix Searching Using Tries

What is a suffix?

A suffix, contrary to prefixes, is the ending substring of a word. Searching for suffixes is an everyday use case for tries, where the strings are generally inverted and inserted into the trie.

A prefix string is a substring of a string or word present at the beginning. Note that a suffix will become a prefix if the string is inverted. For example, for the word bake, the valid prefixes are b, ba, bak, and bake, while the valid suffixes are bake, ake, ke, and e.

What is suffix searching?

Searching for the presence of a suffix in a string is called suffix searching.

For a general use case, one can traverse the string to check if the suffix is present. For example, to check if day is a valid suffix of holiday, one can traverse the word holiday in reverse order and check if yad (which is day in reverse order) is present as a prefix.

But this can be problematic if there's a need to search for suffixes in multiple words. One has to go through all the strings one by one. In cases like these, tries can be very helpful. With a trie, you can search for suffixes of multiple words in a single traversal.

Trie traversal

For suffix-related searches, the trie is traversed for each character of the provided word.

For example, in the visualization given below, we're traversing for the suffix ake in the trie we used initially.