Data Structures & Algorithms

String Algorithms

String problems are often bookkeeping problems in disguise. The goal is to keep the invariant small enough to update in linear time.

8 published notes

2 planned topics

4 advanced or expert notes

basic starting level

Back to DSA Competitive Programming

Category Overview

String Algorithms

Prefix structure, automata, and linear-time matching tools.

Raw TeX

Overview

String algorithms are full of linear-time routines that look mysterious until the maintained boundary becomes clear. The notes in this branch are written to keep that boundary explicit.

Typical Questions

Which prefix or suffix information is enough to continue?
Which transitions are reused from one position to the next?
When is a character comparison paid for once, and when can it repeat too many times?

Difficulty Bands

How this branch is distributed

The labels are not cosmetic. They are there to signal the amount of prerequisite structure and implementation fragility you should expect before opening the note.

basic: 1 intermediate: 3 advanced: 4 expert: 0

1 basic

basic

These are the shortest on-ramp notes in this category and the ones most likely to be usable immediately in contest practice.

KMP

3 intermediate

intermediate

These notes assume the base routine is already familiar and focus on the first real structural upgrades.

Z-Function, Rolling Hash, Trie

4 advanced

advanced

These are the notes where proofs, reductions, or implementation details become the main bottleneck.

Suffix Array, Suffix Automaton, Manacher, Aho-Corasick

Published notes

What is already written

These are the finished note pages in this category, each with rendered TeX, C++ code, references, and practice suggestions.

basic

KMP

Prefix-function based linear-time string matching with no backtracking in the text.

strings pattern matching / prefix function

intermediate

Z-Function

Measure how much each suffix matches the full string, then reuse that linear-time structure for pattern matching and periodicity.

strings linear matching / periodicity

intermediate

Rolling Hash

A fast probabilistic fingerprint for substring comparison, string sets, and prefix-based matching tricks.

hashing substrings / probabilistic

intermediate

Trie

Store strings by prefix so inserts, prefix checks, and dictionary transitions depend on length rather than set size.

prefix tree strings / dictionary

advanced

Suffix Array

Sort all suffixes once, then reuse the order and LCP information for many substring and lexicographic queries.

suffix structures sorting / LCP

advanced

Suffix Automaton

A linear-time substring automaton that is especially good at online extension, distinct-substring counts, and occurrence queries.

suffix structures automaton / substrings

advanced

Manacher

Compute longest odd and even palindromic radii around every center in linear time.

palindrome linear time / string

advanced

Aho-Corasick

A trie with failure links that searches many patterns in one text in a single pass.

multiple patterns automaton / trie

Study Order

Next topics in this branch

These are still intentionally shown as planned or outline topics rather than shallow filler. The branch should feel incomplete in honest places instead of fake-complete everywhere.

Palindromic tree planned Suffix tree outline

Show raw files

Category TeX sourcecompetitive_programming/dsa/string-algorithms/index.tex

String Algorithms

String Algorithms

Overview

Typical Questions

How this branch is distributed

What is already written

KMP

Z-Function

Rolling Hash

Trie

Suffix Array

Suffix Automaton

Manacher

Aho-Corasick

Recommended order to read this branch

KMP

Z-Function

Rolling Hash

Trie

Suffix Array

Suffix Automaton

Manacher

Aho-Corasick

Next topics in this branch

Source Files and Assets