Rare
 0/6

Suffix Array

Author: Benjamin Qi

Quickly Sorting Suffixes of a String (and Applications)

Edit This Page

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

Resources

Implementations

Resources
Benq

O(N log N)

(recommend that you also test against brute force for many small strings)

LCP Array

StatusSourceProblem NameDifficultyTags
YSEasy
Show TagsSuffix Array

Quickly compute longest common prefix of two suffixes.

StatusSourceProblem NameDifficultyTags
PlatHard
Show TagsSuffix Array
CFHard
Show TagsSuffix Array

Burrows-Wheeler Transform

Resources
GFG

could be simpler?

StatusSourceProblem NameDifficultyTags
CSESHard
Show TagsSuffix Array

Run Enumerate

Resources
cp-algo

could be simpler?

(describe how to do easily w/ suffix array)

StatusSourceProblem NameDifficultyTags
YSHard
Show TagsSuffix Array

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!