## Table of Contents

Suffix 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 this page# String Suffix Structures

Authors: Siyong Huang, Benjamin Qi

### Prerequisites

Suffix Automata, Suffix Trees, and Palindromic Trees

## Table of Contents

Suffix 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 this page

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 $\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.

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

Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|

Plat | Hard | ||||||||

With Suffix Automaton

## Suffix Structure Problems (Array, Automaton, Tree)

Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|

CF | Easy | ## Show TagsSuffix Structures | |||||||

Kattis | Easy | ||||||||

onlinejudge.org | Easy | ||||||||

SPOJ | Easy | ## Show TagsSuffix Structures | |||||||

CF | Easy | ||||||||

HE | Normal | ## Show TagsSuffix Structures | |||||||

CF | Normal | ## Show TagsSuffix Structures | |||||||

Balkan OI | Normal | ## Show TagsDP, Suffix Structures | |||||||

CF | Hard | ## Show TagsSuffix Structures | |||||||

CF | Hard | ## Show TagsSuffix Structures | |||||||

CF | Hard | ## Show TagsSuffix Structures | |||||||

CF | Very Hard | ## Show TagsDP, Suffix Structures | |||||||

CF | Very Hard | ## Show TagsSuffix Tree | |||||||

CF | Very Hard | ## Show TagsSuffix Structures | |||||||

## Extending Palindromic Tree

### Problems

Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|

CF | Very Hard | ## Show TagsPalindromic Tree | |||||||

CF | Insane | ## 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!