PrevNext
Has Not Appeared
 0/17

String Suffix Structures

Authors: Siyong Huang, Benjamin Qi

Suffix Automata, Suffix Trees, and Palindromic Trees

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.

Suffix Automaton

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.

Resources
CFExplanation of Suffix Automata
cp-algoExcellent Suffix Automaton tutorial
CFMore problems!

Implementation

Resources
Benq

Suffix Tree

The Suffix Tree is a trie that contains all suffixes of a string. Naively, this would take up O(N2)O(N^2) memory, but path compression enables it to be represented and computed in linear memory.

Resources
SOexample + diagrams
CFbrief explanation of Ukkonen's Algorithm + code

Implementation

Resources
Benqbased off adamant's above
cp-algoimplementation of Ukkonen's Algorithm

Generate Suffix Array from Suffix Tree

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

Generate Suffix Tree from Suffix Array

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.

Pro Tip!

Frequently, string suffix structures are greatly simplified by adding a 'terminator' character, such as $ or -, to the end of the string. In the following samples, these terminators will be explicitly added.

Sample Code: Suffix Tree from Suffix Array

Generate Suffix Tree from Suffix Automaton

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

Example: Standing Out

StatusSourceProblem NameDifficultyTagsSolution
PlatHardExternal Sol

With Suffix Automaton

Suffix Structure Problems (Array, Automaton, Tree)

StatusSourceProblem NameDifficultyTagsSolution
CFEasy
Show Tags

Suffix Structures

Check CF
KattisEasyShow Sketch
onlinejudge.orgEasyView Solution
SPOJEasy
Show Tags

Suffix Structures

Show Sketch
CFEasyCheck CF
HENormal
Show Tags

Suffix Structures

View Solution
CFNormal
Show Tags

Suffix Structures

Check CF
Balkan OINormal
Show Tags

Suffix Structures, DP

CFHard
Show Tags

Suffix Structures

Check CF
CFHard
Show Tags

Suffix Structures

Check CF
CFHard
Show Tags

Suffix Structures

Check CF
CFVery Hard
Show Tags

Suffix Structures, DP

Check CF
CFVery Hard
Show Tags

Suffix Tree

Check CF
CFVery Hard
Show Tags

Suffix Structures

Check CF

Extending Palindromic Tree

Problems

StatusSourceProblem NameDifficultyTagsSolution
CFVery Hard
Show Tags

Palindromic Tree

Check CF
CFInsane
Show Tags

Palindromic Tree

Check CF

Module Progress:

Give Us Feedback on String Suffix Structures!

PrevNext