String Suffix Structures

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.

Implementation

Suffix Tree

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

Implementation

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.

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

Copy
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!

Copy
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

Solution With Suffix Automaton - Standing Out

Copy
#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)

Extending Palindromic Tree

Problems