Search code examples
algorithmsuffix-treeaho-corasick

Are the suffix links in a suffix tree same as the failure edges in an aho-corasick automaton?


If so, can someone explain the purposes of suffix links in a suffix tree for exact string matching ?


Solution

  • There is none. Suffix links are specific transitions in the suffix tree. Given a state in the tree representing a substring (si), with 0 < i < n, the suffix tree from this state will lead to the state representing the substring (si+1), with 0 < i < (n-1).

    These specific transitions are used during the construction of the tree to quickly update the branches of the tree while you add new characters. As their name implies, given a starting state representing a string S, if you keep following the suffix links you will enumerate the suffixes of S.

    And... That's it. You could use that information to quickly perform some queries but there is no relevance to exact string matching.

    How does the exact string matching works in a suffix tree? You walk down your tree. If you're in a node you must select the good transition, starting with the character matching your string. If there is no mismatch, you can end up in an explicit state (a node) or in an implicit state (in the middle of a transition): at this point you know the input string is a substring of the string represented by the suffix tree.