String Fundamentals

The vocabulary and the theory that the algorithms rest on.

Definitions

Term	Meaning
Substring	a contiguous block, $s[i..j]$
Subsequence	any subset of positions, order preserved (not contiguous)
Prefix	$s[\mathrm{0..}i]$ · Proper prefix: not the whole string
Suffix	$s[i..n)$
Border	a string that is both a proper prefix and a proper suffix
Period $p$	$s[i]=s[i+p]$ for all valid $i$
Rotation	$s[i..n)+s[\mathrm{0..}i)$
Palindrome	equal to its own reverse

A string of length $n$ has $\left(\genfrac{}{}{0ex}{}{n+1}{2}\right)$ substrings (not all distinct) and $2^n$ subsequences.

The border-period duality

$s$ has a border of length $b$ iff $s$ has a period $p=n-b$.

This single equivalence is why the prefix function — which computes the longest border of every prefix — is such a powerful primitive. It answers questions about periodicity for free.

All periods. Following the border chain $\pi [n-1],\pi [\pi [n-1]-1],\dots$ enumerates every border, hence every period, in $O(n)$.

Smallest period. $p=n-\pi [n-1]$. The string is a full repetition of that period iff $p\mid n$.

int smallestPeriod(const string& s) {
    vector<int> pi = prefixFunction(s);
    return s.size() - pi.back();
}
bool isRepetition(const string& s) {
    int p = smallestPeriod(s);
    return p != (int)s.size() && s.size() % p == 0;
}

The periodicity lemma (Fine and Wilf)

If $s$ has periods $p$ and $q$ with $p+q\le |s|+\gcd (p,q)$, then it also has period $\gcd (p,q)$.

The bound is tight. This lemma underlies the linear-time constant-space matching algorithms (Galil-Seiferas, Crochemore-Perrin) and the analysis of runs.

Lexicographic order

Compare character by character; if one string is a prefix of the other, the shorter one is smaller. Note that lexicographic order is not length order — "z" > "abc".

• Smallest rotation — Booth’s algorithm or Duval, $O(n)$.
• Comparing substrings in $O(1)$ — hashing plus binary search on the LCP, or a suffix array with rank arrays.
• $k$-th lexicographic substring — descend a suffix automaton with subtree counts.

Counting distinct substrings

Method	Complexity
Suffix array + LCP	$\frac{n(n+1)}{2}-\sum \mathrm{lcp}[i]$, $O(n\log n)$
Suffix automaton	${\sum }_v(\mathrm{len}[v]-\mathrm{len}[\mathrm{link}[v]])$, $O(n)$
Hashing + a set per length	$O(n^2)$
Trie of all suffixes	$O(n^2)$

The suffix automaton formula is the cleanest: each state represents a set of substrings of consecutive lengths, and their count is exactly $\mathrm{len}[v]-\mathrm{len}[\mathrm{link}[v]]$.

Runs and repetitions

A run is a maximal periodic substring with period $p\le |w|/2$.

The runs theorem (Bannai et al., 2015): a string of length $n$ has fewer than $n$ runs, and they can all be found in $O(n)$.

Runs are found via Lyndon roots plus longest-common-extension queries. The older Main-Lorentz $O(n\log n)$ divide and conquer is easier to implement and usually sufficient.

Choosing a tool

Task	Tool
Find one pattern in a text	KMP, Z, or hashing
Find many patterns	Aho-Corasick
Compare arbitrary substrings	hashing, or suffix array + LCP
Count distinct substrings	suffix automaton
Longest common substring of two strings	suffix automaton of one, run the other through it
All palindromic substrings	Eertree or Manacher
Periods and borders	prefix function
Smallest rotation	Booth or Duval
$k$-th substring lexicographically	suffix automaton

See also: Prefix Function · String Hashing · Strings