What are the differences between suffix links and failure links?

Question

I am studying algorithms in this semester and have read about the Aho-Corasick string matching algorithm and Ukkonen's algorithm for building suffix trees.

I read both of them for but can't understand the main basic differences of these two, except that failure links check prefixes and suffix links check suffixes.

What is the difference between these two algorithms?

Answer 1

I think that your understanding of suffix links and failure links is incorrect. In both cases, a suffix/failure link is a pointer from one node in the trie/suffix tree to another node in the trie/suffix tree with the following property: if the original node represents the string x, then the string y encoded by the node pointed at by the suffix/failure link is the node for which y is the longest possible suffix of the string x.

The main difference between the two algorithms is what the algorithms produce rather than what the suffix/failure links mean. Aho-Corasick produces a trie annotated with extra transition information that makes it possible to find all instances of a collection of strings as rapidly as possible. The failure links produced are used both in the construction of the algorithm and in the pattern-matching step. Ukkonen's algorithm produces a suffix tree, using the suffix links only during construction and not during most queries on the tree.

Hope this helps!

Answer 2

The difference is a suffix/dictionary link is like a pointer to the parent of the child. A failure link is from a breadth-first search. Both links are suffixes.