Suffix Array

Author: Benjamin Qi

Quickly Sorting Suffixes of a String (and Applications)

Focus Problem – read through this problem before continuing!

Resources


CF	Suffix Array	Videos & Practice Problems
cp-algo	Suffix Array - Definition & Construction
CPC	11 - Strings (Suffix Array)
CP2	6.6 - Suffix Array and Applications

Resources
	Benq	Suffix Array w/ LCP	O(N log N)

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

Status	Source	Problem Name	Difficulty	Tags
	YS	# of Substrings	Easy	Show Tags Suffix Array

Quickly compute longest common prefix of two suffixes.

Status	Source	Problem Name	Difficulty	Tags
	Plat	Standing Out from the Herd	Hard	Show Tags Suffix Array
	CF	Two Prefixes	Hard	Show Tags Suffix Array

Resources
	GFG	Inverting Burrows-Wheeler Transform	could be simpler?

Status	Source	Problem Name	Difficulty	Tags
	CSES	String Transform	Hard	Show Tags Suffix Array

Resources
	cp-algo	Finding repetitions	could be simpler?

(describe how to do easily w/ suffix array)

Status	Source	Problem Name	Difficulty	Tags
	YS	Run Enumerate	Hard	Show Tags Suffix Array