Table of ContentsSuffix AutomatonImplementationSuffix TreeImplementationGenerate Suffix Array from Suffix TreeGenerate Suffix Tree from Suffix ArrayGenerate Suffix Tree from Suffix AutomatonExample: Standing OutSuffix Structure Problems (Array, Automaton, Tree)Extending Palindromic TreeProblemsEdit with LiveUpdate
String Suffix Structures
Authors: Siyong Huang, Benjamin Qi
Suffix Automata, Suffix Trees, and Palindromic Trees
Table of ContentsSuffix AutomatonImplementationSuffix TreeImplementationGenerate Suffix Array from Suffix TreeGenerate Suffix Tree from Suffix ArrayGenerate Suffix Tree from Suffix AutomatonExample: Standing OutSuffix Structure Problems (Array, Automaton, Tree)Extending Palindromic TreeProblems
Edit with LiveUpdate
A lot of problems can be solved with Suffix Arrays, Suffix Automata, or Suffix Trees. The solution may just be slightly easier/harder with the various data structures.
The Suffix Automaton is a directed acyclic word graph (DAWG), such that each path in the graph traces out a distinct substring of the original string.
The Suffix Tree is a trie that contains all suffixes of a string. Naively, this would take up memory, but path compression enables it to be represented and computed in linear memory.
A suffix array can be generated by the suffix tree by taking the dfs traversal of the suffix tree.
Sample Code: Suffix Array from Suffix Tree
Of course, the above operation can be reversed as well. Each element in the suffix array corresponds to a leaf in the suffix tree. The LCP array stores information about the Lowest Common Ancestor of two adjacent elements in the suffix array. Using these two pieces of information, we can construct the suffix tree from the suffix array in linear time.
Sample Code: Suffix Tree from Suffix Array
One interesting thing about Suffix Trees and Suffix Automata is that the link tree of a Suffix Automaton is equivalent to the Suffix Tree of the reversed string. Since Suffix Automata are much easier to create than Suffix Trees, we can use this as an alternate method to build a Suffix Tree, all in linear time too!
Sample Code: Suffix Tree from Suffix Automaton
With Suffix Automaton
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!
Give Us Feedback on String Suffix Structures!
Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.