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
CF

Explanation of Suffix Automata

cp-algo

Excellent Suffix Automaton tutorial

CF

More 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)\mathcal{O}(N^2) memory, but path compression enables it to be represented and computed in linear memory.

Resources
SO

example + diagrams

CF

brief explanation of Ukkonen's Algorithm + code

Implementation

Resources
Benq

based off adamant's above

cp-algo

implementation 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.

C++

int N, sa[MN], ctr; // length of string, suffix array, counter
struct Edge {
public:
int n, l, r; // node, edge covers s[l..r]
explicit operator bool() const { return n != -1; }
} c[MN * 2][26]; // edges of a suffix tree
void dfs(int n = 0, int d = 0) {
bool c = 0; // Has child. If false, then this node is a leaf

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.

C++

int N;
char s[MN];
int sa[MN]; // suffix array
int lcp[MN]; // lcp[i] stores the longest common prefix between s[sa[i-1]..]
// and s[sa[i]..]
Edge c[MN * 2][MK]; // edges of suffix tree
int d[MN * 2]; // length of string corresponding to a node in the suffix tree
int q[MN * 2], Q, ctr,
rm[MN]; // q is used as stack. ctr counts number of nodes in tree

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!

C++

char s[MN]; // string
int ord[MN]; // nodes representing prefixes of the string s
int u[MN * 2]; // whether the node has already been created
int l[MN * 2]; // link in suffix automaton
Edge c[MN * 2][27]; // edge of suffix tree (not automaton; structure of
// automaton is not necessary to build stree)
void build_tree() {
s[N] = 26; // terminator
for (int i = N; i >= 0; --i) ord[i] = append(ord[i + 1], s[i]);
for (int i = 0, x, r, l; i <= N; ++i) {

Example - Standing Out

Focus Problem – try your best to solve this problem before continuing!

Solution With Suffix Automaton - Standing Out

#include <cstdio>
#include <cstring>
#include <vector>
FILE *IN, *OUT;
typedef long long ll;
const int MN = 1e5 + 10, MM = MN * 2;
char s[MN];
std::vector<int> down[MM];
int N, v[MM], c[MM][26], l[MM], d[MM], topo[MM], T, X;

Suffix Structure Problems (Array, Automaton, Tree)

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsSuffix Structures
KattisEasy
onlinejudge.orgEasy
SPOJEasy
Show TagsSuffix Structures
CFEasy
HENormal
Show TagsSuffix Structures
CFNormal
Show TagsSuffix Structures
Balkan OINormal
Show TagsDP, Suffix Structures
CFHard
Show TagsSuffix Structures
CFHard
Show TagsSuffix Structures
CFHard
Show TagsSuffix Structures
CFVery Hard
Show TagsDP, Suffix Structures
CFVery Hard
Show TagsSuffix Tree
CFVery Hard
Show TagsSuffix Structures

Extending Palindromic Tree

Problems

StatusSourceProblem NameDifficultyTags
CFVery Hard
Show TagsPalindromic Tree
CFInsane
Show TagsPalindromic Tree

Module Progress:

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!

PrevNext