Prefix vs Suffix Trie in String Matching

Question

I'm not too well-versed about the actual algorithms used in string matching with tries.

I'm wondering why there seems to be more focus on suffix tries for string matching rather than prefix tries. Can we not use prefix tries for substring matching also? Put in another way, what are the advantages of suffix tries over prefix tries?

Wandie

Answer 1

.retteb era seirt xiferp ,drawkcab daer uoy fI

Seriously. Suffix tries allow you to traverse from the beginning of a string.

Prophet

Answer 2

I think some of the confusion here arises because the term “suffix trie” means more than just “a trie that holds suffixes.” Rather, a suffix trie typically means “a prefix trie holding all the suffixes of a given string.” This contrasts with “prefix trie,” which typically stores an arbitrary collection of strings rather than all prefixes of a given string.

The reason suffix trees are useful is the following fact, sometimes called the fundamental theorem of stringology:

A string x is a substring of a string w if and only if x is a prefix of a suffix of w.

For example, “irate” is a substring of “pirates” because it’s a prefix of the suffix “irates.”

This fact is why suffix tries are so good at substring searching. Suppose you want to see whether x is a substring of w. And further suppose that, somehow, you obtained a suffix tree for w. Then you can just walk the suffix tree from the root downward and see whether you can read x without falling off the tree. If so, x is a prefix of some suffix of w, so x is a substring of w. If not, x isn’t a prefix of any suffix of w, and so x isn’t a substring of w.

As @Ed Staub’s answer shows, you could just as easily do this by using a trie that stores all the prefixes of w in reverse, then checking if x is a suffix of any prefix of w. But in practice it’s easier to think about holding all the suffixes in a prefix trie and so that’s what we do.

Informer

So the key 'difference' is in other words that suffix trees are actually just an application of prefix trees? – Kovacs

You’re correct that suffix trees are a specific application of prefix trees (a suffix tree is a radix trie of all the suffixes of a string), but the resulting suffix tree has so many interesting properties beyond this that I hesitate to say that this is the only or key fact. – Informer