iii. Theoretical Algorithms Catalog

Named algorithms that matter for the theory (or for production libraries) more than for contests: what each achieves, how, and what to write instead. Asymptotic complexity is not running time: several entries are galactic (faster only for inputs larger than anything that will exist), and Dinic, Kruskal, Hungarian, KMP and NTT beat their “faster” relatives at every contest size.

Area	Algorithm	Result	Write instead
primality	AKS	PRIMES $\in$ P, $\tilde{O}({\log }^{6}n)$	Miller–Rabin
primality	Lucas–Lehmer	Mersenne $2^p-1$ in $p-2$ squarings	(it is the practical test)
factoring	Lenstra ECM	$L_p[\frac{1}{2},\sqrt{2}]$, depends on the smallest factor	Pollard’s rho
factoring	quadratic sieve	$L_n[\frac{1}{2},1]$	Pollard’s rho
sorting	Han; Han–Thorup	$O(n\log \log n)$; $O(n\sqrt{\log \log n})$ expected	radix sort
multiplication	Toom–Cook, Schönhage–Strassen, Fürer, Harvey–van der Hoeven	$n^{1.465}$, $n\log n\log \log n$, $n\log n{2}^{O({\log }^{\ast }n)}$, $n\log n$	Karatsuba / NTT
DFT	Good–Thomas, Rader	no twiddles for coprime factors; prime lengths via convolution	radix-2 FFT / NTT
max flow	Karzanov, MPM, Ahuja–Orlin, Goldberg–Tarjan, Orlin	$O(n^3)$, $O(n^3)$, $O(nm+n^2\log U)$, $O(nm\log \frac{n^2}{m})$, $O(nm)$	Dinic
min-cost flow	Goldberg–Tarjan cost scaling	$O(nm\log n\log (nC))$	SSP with potentials
matching	Gabow scaling, Gabow–Tarjan, Micali–Vazirani	$O(n^{3/4}m\log C)$, $O(\sqrt{n}m\log (nC))$, $O(m\sqrt{n})$	Hungarian, Hopcroft–Karp, blossom
MST	Fredman–Tarjan, Chazelle, Karger–Klein–Tarjan, Pettie–Ramachandran	$m{\log }^{\ast }n$, $m\alpha$, $O(m)$ expected, optimal	Kruskal
dynamic MST / trees	Frederickson (topology trees)	$O(\sqrt{m})$ per update	offline segment tree + rollback DSU
LCA	Harel–Tarjan, Tarjan / Mehlhorn offline	$O(n)/O(1)$; $O((n+q)\alpha )$	binary lifting, Euler tour + sparse table
planar min cut	Reif	$O(n{\log }^{2}n)$, now $O(n\log \log n)$	dual shortest path (Dijkstra)
string matching	Apostolico–Giancarlo, Galil–Seiferas, Crochemore–Perrin (Two-Way)	$\le 2n$ comparisons; $O(1)$ space; $O(1)$ space	KMP / Z
multi-pattern	Commentz–Walter, Wu–Manber	sublinear on average	Aho–Corasick
suffix trees	Weiner, McCreight, Farach	$O(n)$; $O(n)$; $O(n)$ for integer alphabets	suffix automaton / suffix array

Number theory and arithmetic

AKS primality (Agrawal, Kayal, Saxena, 2002)

For $\gcd (a,n)=1$: $n$ is prime $⟺(x+a{)}^n\equiv x^n+a(\mathrm{mod}n)$. Checking this directly costs $O(n)$ coefficients; AKS checks it modulo the small polynomial $x^r-1$ for a bounded range of $a$. Algorithm: (1) if $n=m^k$ with $k>1$, composite; (2) find the smallest $r$ with ${\mathrm{ord}}_r(n)>{\log }^{2}n$; (3) if $1<\gcd (a,n)<n$ for some $a\le r$, composite; (4) if $n\le r$, prime; (5) for $a=\mathrm{1..}\lfloor \sqrt{\phi (r)}\log n\rfloor$, if $(x+a{)}^n\not\equiv x^n+a(\mathrm{mod}{x}^r-1,n)$, composite; (6) prime. $\tilde{O}({\log }^{12}n)$ in the paper, $\tilde{O}({\log }^{6}n)$ with Lenstra–Pomerance, polynomial space. It resolved an old question (primality in P unconditionally; Miller had it only under the generalized Riemann hypothesis) but nobody uses it: deterministic Miller–Rabin with fixed bases takes under a microsecond for 64-bit inputs where AKS takes seconds, and ECPP produces certificates far faster for huge $n$.

Test	Time	Deterministic?	Practical?
trial division	$O(\sqrt{n})$	yes	tiny $n$
Miller–Rabin, fixed bases	$O(k{\log }^{3}n)$	yes for 64-bit	yes: Primality and Factorization
Miller–Rabin, random bases	$O(k{\log }^{3}n)$	error $\le 4^{-k}$	yes
Baillie–PSW	$O({\log }^{3}n)$	no counterexample known	yes
ECPP	heuristic $\tilde{O}({\log }^{4}n)$	yes, with a certificate	huge $n$
AKS	$\tilde{O}({\log }^{6}n)$	yes	no

Proof: the polynomial identity behind AKS

In ${\mathbb{Z}}_n[x]$, $(x+a{)}^n={\sum }_k(\genfrac{}{}{0ex}{}{n}{k})x^k{a}^{n-k}$. If $n$ is prime, $n\mid \left(\genfrac{}{}{0ex}{}{n}{k}\right)$ for $0<k<n$ (the numerator $n!$ has the factor $n$, the denominator does not), and $a^n\equiv a$ by Fermat, so $(x+a{)}^n\equiv x^n+a$. If $n$ is composite with a prime factor $q$, $q^e\parallel n$, then $\left(\genfrac{}{}{0ex}{}{n}{q}\right)$ is not divisible by $q^e$ (the factor $q$ in $n$ is cancelled by the $q$ in $q!$, and no other factor of $q$ appears), so the coefficient of $x^q$ is $\left(\genfrac{}{}{0ex}{}{n}{q}\right)a^{n-q}\not\equiv 0(\mathrm{mod}n)$ when $\gcd (a,n)=1$. AKS’s contribution, quoted here, is that checking the identity modulo $x^r-1$ for the small range of $a$ still certifies primality.

Lucas–Lehmer (Mersenne primes)

With $s_0=4$, $s_{i+1}=s_i^2-2$: for an odd prime $p$, $M_p=2^p-1$ is prime $⟺s_{p-2}\equiv 0(\mathrm{mod}{M}_p)$. Reduction mod $M_p$ needs no division ($2^p\equiv 1$: fold the high bits onto the low ones). $p-2$ squarings of $p$-bit numbers: $O(p^3)$ schoolbook, $\tilde{O}(p^2)$ with FFT / IBDWT multiplication; around $p\approx 8\cdot 10^7$ this is days of GPU time per candidate, which is what GIMPS distributes. Facts: $M_p$ prime needs $p$ prime ($2^a-1\mid 2^{ab}-1$), the converse fails ($M_{11}=2047=23\cdot 89$); 52 Mersenne primes are known; the largest known prime has been a Mersenne prime almost continuously since 1952; even perfect numbers are exactly $2^{p-1}(2^p-1)$ with $M_p$ prime (Euclid–Euler). Relatives: Lucas–Lehmer–Riesel for $k\cdot 2^n-1$, Pépin’s test for Fermat numbers $2^{2^n}+1$.

bool lucasLehmer(int p) {                                // M_p = 2^p - 1 prime? p prime, p <= 61 (i128 products)
    if (p == 2) return true;
    const ull M = (1ULL << p) - 1; ull s = 4;
    auto modM = [&](i128 x) { while (x > (i128)M) x = (x & M) + (x >> p); return (ull)(x == M ? 0 : x); };   // 2^p = 1
    for (int i = 0; i < p - 2; i++) s = modM((i128)s * s + M - 2);   // + M keeps the value non-negative
    return s == 0;
}

Proof: if s_(p-2) is divisible by M_p, then M_p is prime

Let $\omega =2+\sqrt{3}$, $\bar{\omega }=2-\sqrt{3}$, $\omega \bar{\omega }=1$. By induction $s_i={\omega }^{2^i}+{\bar{\omega }}^{2^i}$ (square: $s_i^2={\omega }^{2^{i+1}}+{\bar{\omega }}^{2^{i+1}}+2$). Suppose $M_p\mid s_{p-2}$ and let $q$ be a prime factor of $M_p$ with $q^2\le M_p$ if $M_p$ were composite. In $R={\mathbb{Z}}_q[\sqrt{3}]$ (a ring with $q^2$ elements), ${\omega }^{2^{p-2}}+{\bar{\omega }}^{2^{p-2}}=0$; multiply by ${\omega }^{2^{p-2}}$: ${\omega }^{2^{p-1}}=-1$, so ${\omega }^{2^p}=1$ and $\omega$ has order exactly $2^p$ in the unit group of $R$, which has at most $q^2-1$ elements. Then $2^p\le q^2-1<q^2\le M_p=2^p-1$: a contradiction, so $M_p$ has no prime factor $q\le \sqrt{M_p}$, i.e. it is prime. The converse (prime $\Rightarrow$ divisible) uses that 3 is a non-residue mod $M_p$ ($M_p\equiv 7(\mathrm{mod}12)$) and a Frobenius argument; quoted. The code: modM keeps the residue class because $x=(x\mathrm{mod}{2}^p)+2^p\lfloor x/2^p\rfloor \equiv (x\mathrm{mod}{2}^p)+\lfloor x/2^p\rfloor$. Checked against Miller–Rabin on $M_p$ for all primes $p\le 61$: exactly 2, 3, 5, 7, 13, 17, 19, 31, 61 give primes.

Lenstra’s elliptic curve method (ECM)

Pollard’s $p-1$: if $p-1$ is $B$-smooth then $a^{\mathrm{lcm}(\mathrm{1..}B)}\equiv 1(\mathrm{mod}p)$ and $\gcd (a^k-1,n)$ reveals $p$, but $p-1$ is fixed. Lenstra: replace ${\mathbb{Z}}_p^{\ast }$ by the group of an elliptic curve mod $p$, whose order lies in $[p+1-2\sqrt{p},p+1+2\sqrt{p}]$ (Hasse) and differs from curve to curve: unlimited retries. Pick a random curve and point (choose $x,y,a$ and set $b=y^2-x^3-ax$), compute $kP$ with $k=\mathrm{lcm}(\mathrm{1..}{B}_1)$; point addition needs inverses mod $n$, and a failed inversion hands out $\gcd (\cdot ,n)$, a factor: arithmetic “mod $n$” is a group modulo each prime simultaneously, and the failure happens when $kP=\mathcal{O}$ modulo $p$ but not modulo another factor, i.e. when the curve’s order mod $p$ is $B_1$-smooth. Running time $L_p[\frac{1}{2},\sqrt{2}]=\exp ((\sqrt{2}+o(1))\sqrt{\ln p\ln \ln p})$ in the smallest prime factor $p$, times $O({\log }^{2}n)$ per curve operation: the best method for medium factors (up to 60–70 digits) of huge numbers. Practice: Montgomery curves and the ladder (no inversions in the inner loop), stage 2 (one extra prime between $B_1$ and $B_2$; roughly doubles effectiveness).

Factor digits	$B_1$	Curves
15	2 000	~25
20	11 000	~90
30	250 000	~700
40	3 000 000	~2 400
50	44 000 000	~7 500

Quadratic sieve

Find $x^2\equiv y^2(\mathrm{mod}n)$ with $x\not\equiv \pm y$; then $\gcd (x-y,n)$ is a proper factor (Fermat’s idea). (1) Factor base: primes up to a bound with $\left(\frac{n}{p}\right)=1$ (otherwise $p$ never divides $Q$). (2) $Q(x)=(x+\lceil \sqrt{n}\rceil {)}^2-n$ is small for small $x$, hence often smooth. (3) Sieve: $p\mid Q(x)$ on arithmetic progressions (roots by Tonelli–Shanks); subtract $\log p$ along them and keep entries reaching $\log |Q(x)|$: the entire speed advantage. (4) Collect $k+1$ smooth relations, exponent vectors mod 2. (5) A dependency over ${\mathbb{F}}_2$ exists ($k+1$ vectors in dimension $k$), found by block Lanczos or Wiedemann (huge sparse matrix). (6) Its product is a square on both sides; a trivial gcd happens about half the time, then try another dependency. Time $L_n[\frac{1}{2},1]$, factor base about $L_n[\frac{1}{2},\frac{1}{2}]$ primes. Variants: MPQS (many polynomials), SIQS (self-initialising, the fastest QS). The idea “build relations, then linear algebra over ${\mathbb{F}}_2$” recurs in XOR bases and subset-parity problems.

Digits of $n$	Best method
$\le 19$ (64-bit)	Pollard’s rho
20–60	ECM (especially if some factor is small)
60–100	quadratic sieve
$>100$	general number field sieve, $L_n[\frac{1}{3},1.92]$

Integer sorting in the word RAM

The $\Omega (n\log n)$ bound holds for comparison sorting; the word RAM (arithmetic, bit operations and indexing on $w$-bit words in $O(1)$) is a stronger model. Techniques: packed sorting (several keys per word, sorted by a constant number of word operations, a bitonic network with masks and one multiplication), signature sorting (sort short hashed signatures, then repair ties), fusion trees (Fredman–Willard: branching factor $w^{1/5}$, a node compared in $O(1)$ by “sketch and multiply”; $O(n\log n/\log \log n)$ sorting), range reduction (halve the key length recursively: the $\log \log$). None is usable in practice, but the ideas are: LSD radix sort beats std::sort 3–5 times on large 32-bit arrays (worth a template for $n\ge 10^7$), word packing is bitset optimization, and “sort by a cheap key, then repair ties” is how prefix doubling works.

Algorithm	Time	Space
comparison sort	$\Theta (n\log n)$	$O(1)$–$O(n)$
counting sort	$O(n+U)$	$O(U)$
radix sort, base $2^b$	$O(nw/b)$	$O(n+2^b)$
fusion trees	$O(n\log n/\log \log n)$	$O(n)$
Han (2002)	$O(n\log \log n)$ deterministic	$O(n)$
Han–Thorup	$O(n\sqrt{\log \log n})$ expected	$O(n)$
$O(n)$?	open

void radixSort(vector<uint32_t>& a) {                      // LSD, 4 passes of 8 bits, stable
    vector<uint32_t> b(sz(a));
    for (int shift = 0; shift < 32; shift += 8) {
        int cnt[257] = {};
        for (uint32_t x : a) cnt[((x >> shift) & 255) + 1]++;
        for (int i = 0; i < 256; i++) cnt[i + 1] += cnt[i];
        for (uint32_t x : a) b[cnt[(x >> shift) & 255]++] = x;
        swap(a, b);
    }
}

Proof: LSD radix sort is correct

Induction on passes: after the pass on byte $t$, the array is sorted by the low $8(t+1)$ bits. Counting sort places elements by byte $t$ and is stable (equal bytes keep their previous order, which by induction is sorted by the lower bytes); so elements are ordered by byte $t$ first and by the lower bytes among ties. After 4 passes they are sorted by all 32 bits. Checked against std::sort.

Multiplication: Toom–Cook, Schönhage–Strassen, Fürer

Toom–Cook treats each operand as a polynomial in the split radix $B=2^m$ with $k$ pieces, evaluates both at $2k-1$ small points ($0,\pm 1,\pm 2,\dots ,\infty$ = leading coefficient), multiplies pointwise ($2k-1$ recursive products of size $n/k$), interpolates the $2k-1$ coefficients by a fixed sequence of additions and exact small divisions, and recomposes with carries: $T(n)=(2k-1)T(n/k)+O(n)=\Theta (n^{{\log }_k(2k-1)})$. Karatsuba is $k=2$ (${\log }_{2}3\approx 1.585$), Toom-3 gives ${\log }_{3}5\approx 1.465$, Toom-4 ${\log }_{4}7\approx 1.404$, and $k\to \infty$ approaches 1 while the interpolation constant explodes, so libraries stop around Toom-4 to Toom-8 and switch to FFT. FFT is the same evaluate–multiply–interpolate at $n$ roots of unity, where evaluation and interpolation themselves cost $O(n\log n)$; unbalanced Toom variants handle operands of very different sizes.

// Polynomial product by Toom-3 (exact integer coefficients), schoolbook below 32 terms.
vector<ll> toom3(vector<ll> a, vector<ll> b) {
    int n = max(sz(a), sz(b));
    if (n <= 32) {
        vector<ll> c(sz(a) + sz(b) - 1, 0);
        for (int i = 0; i < sz(a); i++) for (int j = 0; j < sz(b); j++) c[i + j] += a[i] * b[j];
        return c;
    }
    int k = (n + 2) / 3; int na = sz(a), nb = sz(b);
    a.resize(3 * k, 0); b.resize(3 * k, 0);
    auto part = [&](const vector<ll>& v, int i) { return vector<ll>(v.begin() + i * k, v.begin() + (i + 1) * k); };
    auto lin = [&](const vector<ll>& x, ll cx, const vector<ll>& y, ll cy, const vector<ll>& z, ll cz) {
        vector<ll> r(k); for (int i = 0; i < k; i++) r[i] = cx * x[i] + cy * y[i] + cz * z[i]; return r;
    };
    auto a0 = part(a, 0), a1 = part(a, 1), a2 = part(a, 2), b0 = part(b, 0), b1 = part(b, 1), b2 = part(b, 2);
    auto r0 = toom3(a0, b0);                                                     // x = 0
    auto r1 = toom3(lin(a0, 1, a1, 1, a2, 1), lin(b0, 1, b1, 1, b2, 1));         // x = 1
    auto rm = toom3(lin(a0, 1, a1, -1, a2, 1), lin(b0, 1, b1, -1, b2, 1));       // x = -1
    auto r2 = toom3(lin(a0, 1, a1, 2, a2, 4), lin(b0, 1, b1, 2, b2, 4));         // x = 2
    auto ri = toom3(a2, b2);                                                     // x = infinity
    int L = 2 * k - 1; vector<ll> c(6 * k - 1, 0);
    for (int i = 0; i < L; i++) {                        // interpolate c0..c4 of degree-4 C(x) at 0, 1, -1, 2, inf
        ll v0 = r0[i], v1 = r1[i], vm = rm[i], v2 = r2[i], vi = ri[i];
        ll c0 = v0, c4 = vi;
        ll e = (v1 + vm) / 2 - c0 - c4;                  // c2
        ll o = (v1 - vm) / 2;                            // c1 + c3
        ll t = (v2 - c0 - 4 * e - 16 * c4) / 2;          // c1 + 4 c3
        ll c3 = (t - o) / 3, c1 = o - c3;
        ll cs[5] = {c0, c1, e, c3, c4};
        for (int j = 0; j < 5; j++) c[i + j * k] += cs[j];
    }
    c.resize(na + nb - 1);
    return c;
}

Schönhage–Strassen (1971): an FFT over $\mathbb{Z}/(2^k+1)$, where $2$ is a $2k$-th root of unity ($2^k\equiv -1$), so every twiddle multiplication is a shift; split into $2^{\ell }$ blocks, transform with shifts only ($O(n\log n)$ bit operations), multiply pointwise by recursion on $k$-bit numbers, inverse transform, carry: $T(n)=O(\sqrt{n})T(O(\sqrt{n}))+O(n\log n)=O(n\log n\log \log n)$ (the recursion depth is the $\log \log$). GMP uses it above roughly 30 000–100 000 bits (Toom variants below): the only sub-quadratic asymptotic improvement that is both production code and asymptotically strong. The contest instinct it teaches: choose an algebraic setting where the expensive operation becomes cheap (an NTT-friendly prime like 998244353).

Fürer (2007): $O(n\log n\cdot 2^{O({\log }^{\ast }n)})$ in the ring $\mathbb{C}[x]/(x^P+1)$, which has both cheap roots of unity (powers of $x$: shifts) and expensive ordinary ones, arranged so that only $O({\log }^{\ast }n)$ levels use the expensive ones. ${\log }^{\ast }n\le 5$ below $2^{65536}$, but it was never competitive: a galactic algorithm. Harvey and van der Hoeven (2019) reached $O(n\log n)$, the conjectured optimum, building on Fürer’s mix of cheap and expensive roots; it beats Schönhage–Strassen only beyond about $2^{1729^{12}}$ bits.

Year	Multiplication	Time
antiquity	schoolbook	$O(n^2)$
1960	Karatsuba	$O(n^{1.585})$
1963	Toom–Cook	$O(n^{1+\epsilon })$
1971	Schönhage–Strassen	$O(n\log n\log \log n)$
2007	Fürer	$O(n\log n{2}^{O({\log }^{\ast }n)})$
2019	Harvey–van der Hoeven	$O(n\log n)$

Operand size (limbs, GMP-style)	Method
$<30$	schoolbook
30–300	Karatsuba
300–1000	Toom-3
1000–3000	Toom-4 / 6.5 / 8.5
$>3000$	Schönhage–Strassen / FFT

Galactic algorithm	Beats the practical option only for	Practical?
Fürer multiplication	astronomically large $n$	no
Harvey–van der Hoeven	$n>2^{1729^{12}}$	no
Coppersmith–Winograd-type matrix multiplication	enormous matrices	no
Pettie–Ramachandran MST	unanalysable	no
Chen et al. $m^{1+o(1)}$ max flow	not yet	no
AKS primality	never	no

Proof: the Toom-3 interpolation

$C(x)=A(x)B(x)=c_0+c_{1}x+c_2{x}^2+c_3{x}^3+c_4{x}^4$ (per coefficient block). The five products are $C(0)=c_0$, $C(\infty )=c_4$, $C(1)=\sum c_j$, $C(-1)=c_0-c_1+c_2-c_3+c_4$, $C(2)=c_0+2c_1+4c_2+8c_3+16c_4$. Hence $\frac{C(1)+C(-1)}{2}=c_0+c_2+c_4$ gives $c_2$; $\frac{C(1)-C(-1)}{2}=c_1+c_3$; $\frac{C(2)-c_0-4c_2-16c_4}{2}=c_1+4c_3$; subtracting gives $3c_3$, then $c_1$. All divisions are exact (they divide integers that are multiples by construction). Block $j$ of the product contributes to positions $i+jk$, which is the recomposition. Checked against schoolbook multiplication for random polynomials up to degree 500.

Transforms

Good–Thomas (prime-factor algorithm)

For $n=n_1{n}_2$ with $\gcd (n_1,n_2)=1$, map the input index by the CRT ($j\leftrightarrow (j\mathrm{mod}{n}_1,j\mathrm{mod}{n}_2)$) and the output index by the Ruritanian map ($k=k_1{n}_2+k_2{n}_1\mathrm{mod}n$); then ${\omega }_n^{jk}={\omega }_{n_1}^{j_1{k}_1}{\omega }_{n_2}^{j_2{k}_2}$ with no cross terms, and the 1-D DFT becomes a 2-D DFT on an $n_1\times n_2$ grid: transform the columns, then the rows. Strictly fewer multiplications than Cooley–Tukey (no twiddle stage) at the price of cache-unfriendly index permutations. FFTW’s planner combines Good–Thomas (coprime factors), Cooley–Tukey (non-coprime factors, with twiddles), Rader (prime factors), Bluestein (the general fallback, Convolution Variants) and hard-coded codelets, which is why it is fast at lengths like $1008=16\cdot 63$. The reusable idea is the CRT index map: a problem of size $n_1{n}_2$ with coprime factors becomes independent multi-dimensional pieces (modular arithmetic split into prime powers, counting over ${\mathbb{Z}}_n$, multiplicative functions). Winograd’s FFT pushes the multiplication count lower with minimal convolution algorithms for small sizes.

Rader (prime lengths)

For a prime $p$ with primitive root $g$, re-index $j=g^a$, $k=g^{-b}$ ($k\ne 0$): $X_{g^{-b}}-x_0={\sum }_{a=0}^{p-2}{x}_{g^a}{\omega }^{g^{a-b}}$, a cyclic convolution of length $p-1$ of $x_{g^a}$ with ${\omega }^{g^c}$, computed by an FFT (or Bluestein if $p-1$ factors badly), plus $X_0={\sum }_j{x}_j$: $O(p\log p)$. Reusable move: re-index by a primitive root to turn multiplication into addition (discrete logarithms, Pohlig–Hellman, convolution over ${\mathbb{Z}}_p^{\ast }$ under multiplication: Primitive Roots).

	Rader	Bluestein
requires	a primitive root mod $p$	nothing
convolution length	$p-1$ (exact, cyclic)	$\ge 2p-1$ (padded, linear)
accuracy	better	chirp factors grow, slightly worse
generality	prime lengths	any length
used by FFTW for	moderate primes	large or awkward primes

using cd = complex<double>;
vector<cd> naiveDFT(const vector<cd>& x) {
    int n = sz(x); vector<cd> X(n); const double PI = acos(-1.0);
    for (int k = 0; k < n; k++) for (int j = 0; j < n; j++) X[k] += x[j] * polar(1.0, -2 * PI * j * k / n);
    return X;
}
 
vector<cd> goodThomasDFT(const vector<cd>& x, int n1, int n2) {   // gcd(n1, n2) = 1; sub-DFTs done naively here
    int n = n1 * n2; vector<vector<cd>> g(n1, vector<cd>(n2));
    for (int j = 0; j < n; j++) g[j % n1][j % n2] = x[j];        // CRT input map
    for (int r = 0; r < n1; r++) g[r] = naiveDFT(g[r]);           // length-n2 DFTs
    for (int c = 0; c < n2; c++) { vector<cd> col(n1); for (int r = 0; r < n1; r++) col[r] = g[r][c]; col = naiveDFT(col); for (int r = 0; r < n1; r++) g[r][c] = col[r]; }
    vector<cd> X(n);
    for (int k1 = 0; k1 < n1; k1++) for (int k2 = 0; k2 < n2; k2++) X[(k1 * n2 + k2 * n1) % n] = g[k1][k2];   // Ruritanian output map
    return X;
}
 
vector<cd> raderDFT(const vector<cd>& x, int g) {                // prime length p, primitive root g; cyclic convolution done naively
    int p = sz(x); const double PI = acos(-1.0);
    vector<int> pw(p - 1); pw[0] = 1; for (int i = 1; i < p - 1; i++) pw[i] = (ll)pw[i - 1] * g % p;
    vector<cd> A(p - 1), B(p - 1), X(p);
    for (int a = 0; a < p - 1; a++) A[a] = x[pw[a]];
    for (int c = 0; c < p - 1; c++) B[c] = polar(1.0, -2 * PI * pw[c] / p);   // omega^(g^c)
    for (int j = 0; j < p; j++) X[0] += x[j];
    for (int b = 0; b < p - 1; b++) {                    // X[g^{-b}] = x0 + sum_a A[a] B[a - b]
        cd s = 0; for (int a = 0; a < p - 1; a++) s += A[a] * B[((a - b) % (p - 1) + (p - 1)) % (p - 1)];
        X[pw[(p - 1 - b) % (p - 1)]] = x[0] + s;
    }
    return X;
}

Proof: the Good–Thomas and Rader re-indexings

Good–Thomas. Write $j_1=j\mathrm{mod}{n}_1$, $j_2=j\mathrm{mod}{n}_2$ (a bijection by the CRT) and $k=k_1{n}_2+k_2{n}_1\mathrm{mod}n$ (also a bijection: modulo $n_1$ it is $k_1{n}_2$ with $n_2$ invertible, modulo $n_2$ it is $k_2{n}_1$). With $j=j_1+a{n}_1$, $j{k}_1{n}_2=j_1{k}_1{n}_2+a{k}_{1}n\equiv j_1{k}_1{n}_2(\mathrm{mod}n)$, and likewise $j{k}_2{n}_1\equiv j_2{k}_2{n}_1$. Hence ${\omega }_n^{jk}={\omega }_n^{j_1{k}_1{n}_2}{\omega }_n^{j_2{k}_2{n}_1}={\omega }_{n_1}^{j_1{k}_1}{\omega }_{n_2}^{j_2{k}_2}$: the length-$n$ DFT is exactly the 2-D DFT of the $n_1\times n_2$ array, read out at the Ruritanian positions. Rader. $j\mapsto$ the exponent $a$ with $j=g^a$ is a bijection of $\{\mathrm{1..}p-1\}$ onto $\{\mathrm{0..}p-2\}$; for $k=g^{-b}$, $jk=g^{a-b}$, so $X_k=x_0+{\sum }_a{x}_{g^a}{\omega }^{g^{a-b}}$, which depends on $a-b$ modulo $p-1$: a cyclic correlation, computed in the code directly. Both functions agree with the direct DFT on random inputs ($n_1{n}_2\le 35$, primes up to 31).

Flows and matching

Karzanov (1974) introduced the preflow (inflow $\ge$ outflow, vertices may hold excess): within each level graph, saturate the source edges, push excess forward by increasing level, return what cannot reach $t$ by decreasing level, until no excess remains (a blocking flow); $O(n^2)$ per blocking flow, $O(n^3)$ total, $O(n^2)$ space with a matrix. Goldberg–Tarjan’s push-relabel (1986) kept the preflow and replaced the level graph by a height function with purely local operations (parallelizable and, with highest-label and gap heuristics, the fastest family in practice). Karzanov also proved the $O(m\sqrt{n})$ bound for unit-capacity Dinic and worked on multicommodity flow.

Malhotra–Kumar–Maheshwari (MPM, 1978): blocking flow in $O(n^2)$ via vertex potentials $p(v)=\min (\text{in-capacity},\text{out-capacity})$ in the level graph ($p(s)$, $p(t)$ count one side). The minimum-potential vertex can push its whole $p(v^{\ast })$ forward to $t$ and pull it back from $s$ greedily (no vertex can block that amount); then it is saturated and deleted with all zero-potential vertices. Each vertex is deleted once, each push saturates an edge or exhausts $p(v^{\ast })$, and potential updates cost $O(n)$ per deletion with a matrix: $O(n^2)$ per phase, $O(n^3)$ total. Dinic’s $O(n^{2}m)$ is famously pessimistic; MPM’s value is the guarantee on dense graphs with large capacities.

Graph	Dinic	MPM
sparse, $m=O(n)$	$O(n^3)$	$O(n^3)$
dense, $m=\Theta (n^2)$	$O(n^4)$	$O(n^3)$
unit capacities, bipartite matching	$O(m\sqrt{n})$	$O(n^3)$

Capacity scaling works in phases $\Delta =2^{\lfloor \log U\rfloor },\dots ,1$, augmenting only along residual capacities $\ge \Delta$: Ford–Fulkerson becomes $O(m^2\log U)$, Dinic $O(nm\log U)$. Ahuja–Orlin scales the excess instead: in phase $\Delta$ process only nodes with excess $\ge \Delta /2$, push from the large-excess node of smallest height, and never push more than $\Delta -e(w)$ into $w$; this caps non-saturating pushes at $O(n^2)$ per phase: $O(nm+n^2\log U)$. Goldberg–Tarjan: push-relabel with dynamic trees pushes along whole paths in $O(\log n)$: $O(nm\log \frac{n^2}{m})$. Orlin (2013) with King–Rao–Tarjan: $O(nm)$ for all densities (Orlin for $m=O(n^{16/15-\epsilon })$ by compaction of already-determined parts, excess scaling, dynamic trees and an abundance argument; KRT for denser graphs). Chen, Kyng, Liu, Peng, Probst Gutenberg, Sachdeva (2022): $m^{1+o(1)}$ for max flow and min-cost flow, via interior-point methods with dynamic data structures; purely theoretical.

Max flow	Time
Ford–Fulkerson	$O(mF)$, pseudo-polynomial
Edmonds–Karp	$O(n{m}^2)$
capacity-scaling Ford–Fulkerson	$O(m^2\log U)$
Dinic	$O(n^{2}m)$; unit capacities $O(m\min (\sqrt{m},n^{2/3}))$, unit networks $O(m\sqrt{n})$
Karzanov, MPM, push-relabel FIFO	$O(n^3)$
push-relabel highest label	$O(n^2\sqrt{m})$
Ahuja–Orlin	$O(nm+n^2\log U)$
Goldberg–Tarjan (dynamic trees)	$O(nm\log \frac{n^2}{m})$
Orlin + King–Rao–Tarjan	$O(nm)$
Chen et al.	$m^{1+o(1)}$

Min-cost flow by cost scaling (Goldberg–Tarjan): with potentials $\pi$, reduced costs $c^{\pi }(u,v)=c(u,v)+\pi (u)-\pi (v)$; a flow is $\epsilon$-optimal if every residual arc has $c^{\pi }\ge -\epsilon$ (0-optimal = optimal by complementary slackness). Start with $\epsilon =C$ and the zero flow, refine to $\frac{\epsilon }{2}$-optimality with a push-relabel loop where “admissible” means $c^{\pi }<0$, and stop when $\epsilon <\frac{1}{n}$: integer reduced costs summed around a cycle of at most $n$ arcs cannot reach $-1$, so the flow is optimal. $O(\log (nC))$ phases, each $O(nm\log n)$ with dynamic trees ($O(n^{2}m)$ without).

Min-cost flow	Time	Notes
cycle cancelling	$O(n{m}^{2}CU)$	simple, pseudo-polynomial
min-mean cycle cancelling	$O(n^2{m}^3\log n)$	strongly polynomial (Goldberg–Tarjan, using Karp’s min-mean cycle)
SSP with potentials (Bellman–Ford once, then Dijkstra on reduced costs)	$O(Fm\log n)$	write this: Min-Cost Flow
capacity-scaling SSP	$O(m^2\log n\log U)$
Goldberg–Tarjan cost scaling	$O(nm\log n\log (nC))$	fast general purpose
network simplex	exponential worst case	often fastest in practice

Gabow’s bit scaling: with $C=\max w$, solve for the top $k$ bits $w_k(e)=\lfloor w(e)/2^{\lceil \log C\rceil -k}\rfloor$; since $w_{k+1}\in \{2w_k,2w_k+1\}$, a doubled optimal solution is within $O(n)$ of optimal and $O(n)$ augmentations repair it; after $\lceil \log C\rceil$ rounds it is exact. $\log C$ replaces a factor $C$ (pseudo-polynomial becomes weakly polynomial). It works whenever doubling preserves near-optimality and repair is cheap: max weight perfect matching in general graphs $O(n^{3/4}m\log C)$ (versus $O(n^3)$ or $O(nm\log n)$ blossom), bipartite $O(\sqrt{n}m\log (nC))$; Goldberg’s scaling shortest paths with negative weights $O(m\sqrt{n}\log C)$, and the near-linear $\tilde{O}(m{\log }^{8}n\log C)$ of Bernstein, Nanongkai and Wulff-Nilsen (2022). The contest idea that survives: solve the high bits first, then refine (build an answer from the most significant bit down, checking feasibility).

Gabow–Tarjan: the assignment problem by cost scaling in $O(\sqrt{n}m\log (nC))$: maintain $\epsilon$-optimal dual prices ($c(u,v)-y(u)-y(v)\ge -\epsilon$), halve $\epsilon$ each phase and repair with Hopcroft–Karp-style phases of vertex-disjoint augmenting paths (the $\sqrt{n}$), stop at $\epsilon <\frac{1}{n}$. Separately, linear-time union-find when the union tree is known in advance: micro-trees of $O(\log n)$ vertices solved by table lookup (four Russians), ordinary DSU on the $O(n/\log n)$ macro nodes; this makes Tarjan’s offline LCA truly linear and underlies linear MST verification.

Assignment	Time
all permutations	$O(n!)$
bitmask DP	$O(2^{n}n)$, best for $n\le 20$ with irregular costs
Hungarian	$O(n^3)$, ~40 lines, well under a second for $n\le 500$: Assignment Problem
MCMF with potentials	$O(nm\log n)$
Gabow–Tarjan	$O(\sqrt{n}m\log (nC))$

Micali–Vazirani (1980): maximum matching in general graphs in $O(m\sqrt{n})$, matching Hopcroft–Karp: $O(\sqrt{n})$ phases of maximal sets of vertex-disjoint shortest augmenting paths (after $\sqrt{n}$ phases paths are longer than $\sqrt{n}$, and at most $\sqrt{n}$ disjoint ones remain), each phase $O(m)$. Blossoms break the layering; instead of contracting them it keeps evenlevel and oddlevel per vertex, detects blossoms as bridges (edges whose endpoint levels are inconsistent with a layering) and runs a “double depth-first search”. One of the hardest correct algorithms to implement: the original proof was incomplete, a full proof came in 1994 (Vazirani), and few correct implementations exist.

Matching	Algorithm	Time
bipartite, small	Kuhn	$O(nm)$
bipartite	Hopcroft–Karp or Dinic	$O(m\sqrt{n})$
bipartite, weighted	Hungarian	$O(n^3)$
general	blossom (randomized order)	$O(n^3)$ or $O(nm\alpha )$: General Matching
general	Micali–Vazirani	$O(m\sqrt{n})$
general, weighted	Blossom V (Kolmogorov)	$O(n^3)$, practical
perfect matching exists?	Tutte matrix, random determinant	$O(n^{\omega })$ randomized, 15 lines

Trees and graphs

MST. Chazelle (2000): $O(m\alpha (m,n))$ deterministic, using soft heaps (insert, meld, extract-min in $O(1)$ amortized while corrupting at most an $\epsilon$ fraction of keys, i.e. increasing their stored values), Borůvka contractions, a hierarchy of contractible subgraphs guided by a $t$-ary tree chosen so corruption stays controlled, and recursive clean-up of the corrupted “bad” edges. Soft heaps also give a clean $O(n)$ selection algorithm. Pettie–Ramachandran (2002): provably optimal, running in $\Theta ({\mathcal{T}}^{\ast }(m,n))$, the unknown decision-tree complexity of MST ($\Omega (m)\le {\mathcal{T}}^{\ast }\le O(m\alpha )$): partition into subgraphs of $r=O(\log \log \log n)$ vertices (Borůvka plus soft heaps), look up a precomputed optimal decision tree for each (all found by brute force in $o(n)$ because $r$ is tiny), contract and recurse. The open problem is now to analyse it, and to find a deterministic $O(m)$ algorithm; MST verification is deterministic $O(m)$ (King). Its “table lookup on tiny subproblems” is the four-Russians idea of Farach-Colton–Bender RMQ, $O(n^3/\log n)$ Boolean matrix multiplication and block-precomputed bitset DP.

Year	MST	Time
1926	Borůvka	$O(m\log n)$, parallelizable
1956/57	Kruskal, Prim	$O(m\log n)$; Prim with Fibonacci heap $O(m+n\log n)$
1975	Yao	$O(m\log \log n)$
1984	Fredman–Tarjan	$O(m{\log }^{\ast }n)$
1986	Gabow, Galil, Spencer, Tarjan	$O(m\log {\log }^{\ast }n)$
1995	Karger–Klein–Tarjan	$O(m)$ expected
2000	Chazelle	$O(m\alpha (m,n))$
2002	Pettie–Ramachandran	optimal, value unknown

Fredman–Tarjan: Prim with a Fibonacci heap, but each growth phase stops when the heap exceeds a threshold $k$, the grown trees are contracted, and the next pass uses threshold $2^{2m/k}$: $O({\log }^{\ast }n)$ passes. Frederickson: topology trees cluster a bounded-degree tree into $O(1)$-vertex clusters recursively ($O(\log n)$ levels): $O(\log n)$ path and subtree aggregates, link and cut, plus non-local information such as “minimum edge crossing a cut”. Dynamic MST: insertion of $(u,v,w)$ adds the edge or swaps it with the heaviest edge on the tree path (path max, $O(\log n)$); deleting a tree edge needs the minimum replacement across the cut, which the ambivalent data structure finds in $O(\sqrt{m})$; sparsification (Eppstein, Galil, Italiano, Nissenzweig) improves this to $O(\sqrt{n})$.

Dynamic connectivity / MST	Best known	Technique
incremental connectivity	$O(\alpha )$ amortized	DSU
decremental connectivity on trees	$O(1)$ amortized	Euler tour tricks
fully dynamic connectivity	$O({\log }^{2}n)$ amortized	Holm–de Lichtenberg–Thorup
fully dynamic MST	$O({\log }^{4}n)$ amortized	HDT extension
Frederickson	$O(\sqrt{m})$ worst case	topology trees
offline dynamic connectivity	$O({\log }^{2}n)$	segment tree over time + rollback DSU: ~60 lines, write this: Dynamic Connectivity

LCA. Harel–Tarjan (1984) gave the first $O(n)$ / $O(1)$ LCA: heavy-path decomposition, embedding into a complete binary tree where LCA of inorder labels comes from the highest differing bit (one XOR and one clz), and per-node words recording which path levels contain an ancestor. Then Schieber–Vishkin (1988, simplified and parallelizable), Berkman–Vishkin (1993, reduction to $\pm 1$ RMQ), Farach-Colton–Bender (2000, $\pm 1$ RMQ + four Russians: the standard exposition; 2004 further simplified with a sparse table on blocks). Tarjan’s offline LCA (presented in Mehlhorn’s textbook) answers known queries in $O((n+q)\alpha )$ with a DSU; if the tree grows by leaves, use an Euler tour in a balanced BST; under link and cut, link-cut trees. “Sort the queries so a cheap incremental structure suffices” generalizes far beyond LCA (Mo’s algorithm, offline BIT sweeps, offline dynamic connectivity). Related: level ancestor in $O(n)/O(1)$ (ladder decomposition), tree distance $d_u+d_v-2d_{\mathrm{lca}}$, virtual trees (LCA of consecutive nodes in DFS order).

LCA need	Method	Cost
queries known in advance	offline union-find	$O((n+q)\alpha )$
online, also $k$-th ancestor and path aggregates	binary lifting (the default)	$O(n\log n)$ / $O(\log n)$
$O(1)$ queries	Euler tour + sparse table	$O(n\log n)$ / $O(1)$
$O(n)$ preprocessing	Farach-Colton–Bender	$O(n)$ / $O(1)$
path updates and queries	HLD + segment tree	$O({\log }^{2}n)$
tree grows by leaves / link and cut	Euler tour in a BST / link-cut tree	$O(\log n)$

// Tarjan's offline LCA: queries[u] = {(v, id)}; iterative DFS from root, DSU tagged with the current ancestor.
vector<int> offlineLCA(int n, const vector<vector<int>>& adj, int root, const vector<pair<int, int>>& qs) {
    vector<int> dsu(n), anc(n), ans(sz(qs)), parent(n, -1), it(n, 0); vector<char> done(n, 0), seen(n, 0);
    iota(all(dsu), 0);
    auto find = [&](int x) { while (dsu[x] != x) x = dsu[x] = dsu[dsu[x]]; return x; };
    vector<vector<pair<int, int>>> at(n);
    for (int i = 0; i < sz(qs); i++) at[qs[i].first].push_back({qs[i].second, i}), at[qs[i].second].push_back({qs[i].first, i});
    vector<int> st{root}; seen[root] = 1; anc[root] = root;
    while (!st.empty()) {
        int u = st.back();
        if (it[u] < sz(adj[u])) {
            int v = adj[u][it[u]++];
            if (!seen[v]) { seen[v] = 1; parent[v] = u; anc[v] = v; st.push_back(v); }
        } else {                                         // u finished
            done[u] = 1;
            for (auto [v, id] : at[u]) if (done[v]) ans[id] = anc[find(v)];
            st.pop_back();
            if (parent[u] >= 0) { int p = parent[u]; dsu[find(u)] = find(p); anc[find(p)] = p; }
        }
    }
    return ans;
}

Proof: offline LCA

Invariant: when $u$ finishes, every finished vertex $v$ belongs to the DSU set of the deepest ancestor $a$ of $v$ that is still on the DFS stack, and that set is tagged with $a$ (finished subtrees are merged into their parent, retagged with the parent, at the moment they finish). For a query $(u,v)$ answered when the later of the two finishes, say $u$ with $v$ already finished, the deepest stack ancestor of $v$ is an ancestor of $u$ too (the stack is the root-to-$u$ path), and it is the deepest common one: $\mathrm{LCA}(u,v)$. With path compression (union by size is omitted for brevity) the cost is near-linear. Checked against a brute-force LCA on random trees.

Reif: planar minimum cut via planar duality: cuts in $G$ correspond to cycles in the dual $G^{\ast }$ (one vertex per face, an edge per primal edge), so the minimum cut is the minimum-weight dual cycle, found by divide and conquer on a planar separator ($O(\sqrt{n})$ vertices, balanced halves; a minimum cycle avoids it or crosses it, handled by shortest paths from separator vertices): $O(n{\log }^{2}n)$, later $O(n\log \log n)$ (Chalermsook–Fakcharoenphol–Nanongkai; Italiano et al.). The $s$-$t$ version is the contest one: an $s$-$t$ min cut in a planar graph is a shortest path in the dual between the two outer faces, so “block every path from left to right at minimum cost” on a grid is Dijkstra on the dual grid; image segmentation by graph cuts started here.

Graph	Min cut
general	Stoer–Wagner $O(nm+n^2\log n)$; Karger randomized $O(m{\log }^{3}n)$: Global Min Cut
planar, undirected	$O(n\log \log n)$
planar $s$-$t$ max flow	$O(n\log n)$ (Borradaile–Klein)

Primal $G$	Dual $G^{\ast }$
cut	cycle
$s$-$t$ min cut	shortest path between two faces
spanning tree	the complement edges form a spanning tree of the dual
face	vertex

Strings

Boyer–Moore family. Plain Boyer–Moore can re-compare text characters ($\Theta (nm)$ for aaaa in aaa…a). Apostolico–Giancarlo stores $S[i]$, the match length that ended at text position $i$ in an earlier alignment, and the pattern’s self-overlap table $N[j]$ (longest common suffix of pattern[0..j] and the pattern): if $S[i]>N[j]$ a mismatch is certain, if $S[i]<N[j]$ a match of length $S[i]$ is certain and skipped, if equal resume comparing: $\le 2n$ comparisons, $O(m+\sigma )$ preprocessing, $O(n+m)$ space (the $S$ array is the price, unwelcome for streams), sublinear on typical text. Horspool and Sunday (bad-character rule only) are faster in practice.

Variant	Worst case	Extra space	Notes
Boyer–Moore	$O(nm)$	$O(m+\sigma )$	the original
Boyer–Moore–Horspool	$O(nm)$	$O(\sigma )$	bad character only; fastest in practice
Sunday (quick search)	$O(nm)$	$O(\sigma )$	looks one past the window
Boyer–Moore–Galil	$O(n)$	$O(m+\sigma )$	linear for all-occurrence reporting
Apostolico–Giancarlo	$\le 2n$ comparisons	$O(n+m)$	general guarantee
KMP	$O(n+m)$	$O(m)$	never skips, always linear

Constant-space matching. Galil–Seiferas (1983): linear time, $O(1)$ extra space (no failure function), $\le 5n$ comparisons, via a decomposition $P=uv$ with $v$ highly periodic (a mismatch in $v$ is resolved by the period, a single integer) and $u$ short, computed with the critical factorisation theorem: every string has a position where the local period equals the global period. Crochemore–Perrin Two-Way (1991): the practical descendant, used by glibc’s strstr and memmem: find a critical position from the maximal suffixes under both alphabet orders ($O(m)$ time, $O(1)$ space), scan the right part left to right (mismatch at offset $j$: shift by $j+1$), then the left part right to left (mismatch: shift by the period), remembering one integer of verified prefix so characters are not re-compared: $O(n)$, at most $2n-m$ comparisons. Karp–Rabin is $O(1)$ space but only expected linear. The same periodicity theory underlies runs, Lyndon factorisation and linear-time maximal repetitions; constant-space matching matters for embedded and streaming settings.

// Crochemore-Perrin Two-Way: all occurrences of x in y with O(1) extra space.
vector<int> twoWaySearch(const string& x, const string& y) {
    int m = sz(x), n = sz(y); vector<int> res;
    if (m == 0) { for (int j = 0; j <= n; j++) res.push_back(j); return res; }
    auto maxSuf = [&](bool rev, int& per) {             // maximal suffix under < (rev: under >), and its period
        int ms = -1, j = 0, k = 1; per = 1;
        while (j + k < m) {
            char a = x[j + k], b = x[ms + k];
            if (rev ? a > b : a < b) { j += k; k = 1; per = j - ms; }
            else if (a == b) { if (k != per) k++; else { j += per; k = 1; } }
            else { ms = j; j = ms + 1; k = per = 1; }
        }
        return ms;
    };
    int p, q, i = maxSuf(false, p), jj = maxSuf(true, q);
    int ell = i > jj ? i : jj, per = i > jj ? p : q;     // critical position and its local period
    if (ell + 1 + per <= m && x.compare(0, ell + 1, x, per, ell + 1) == 0) {   // periodic pattern
        int j = 0, memory = -1;
        while (j <= n - m) {
            int t = max(ell, memory) + 1;
            while (t < m && x[t] == y[t + j]) t++;
            if (t >= m) {
                t = ell;
                while (t > memory && x[t] == y[t + j]) t--;
                if (t <= memory) res.push_back(j);
                j += per; memory = m - per - 1;
            } else { j += t - ell; memory = -1; }
        }
    } else {
        per = max(ell + 1, m - ell - 1) + 1;
        int j = 0;
        while (j <= n - m) {
            int t = ell + 1;
            while (t < m && x[t] == y[t + j]) t++;
            if (t >= m) {
                t = ell;
                while (t >= 0 && x[t] == y[t + j]) t--;
                if (t < 0) res.push_back(j);
                j += per;
            } else j += t - ell;
        }
    }
    return res;
}

Crochemore’s repetitions algorithm (1981): all maximal repetitions (runs: maximal substrings of period $p\le |w|/2$) in $O(n\log n)$ by refining the partition of positions by length-$2^k$ substrings (the idea of prefix doubling for suffix arrays and of Hopcroft’s DFA minimisation); classes with positions at distance $\le 2^k$ reveal repetitions. Main–Lorentz finds all squares in $O(n\log n)$ by divide and conquer, more easily. The runs theorem (Bannai et al., 2015): fewer than $n$ runs, all found in $O(n)$ via Lyndon roots (Runs and Periodicity). Repetition detection is the core of LZ-family compression.

Multi-pattern matching. Commentz–Walter (1979): a trie of the reversed patterns walked right to left within a window of the shortest pattern length, with two generalized good-suffix shift functions and a bad-character table: sublinear on average, worst case $O(n\cdot m_{\max })$, space $O(\sigma \sum |P_i|)$; used by early fgrep; superseded. Wu–Manber: with $m$ the shortest pattern length and blocks of $B=2$–$3$ characters, a SHIFT table says how far the window may jump for each block ($m-B+1$ if the block occurs in no pattern prefix of length $m$, else $m-1-$ its rightmost end position), a HASH table lists patterns whose length-$m$ prefix ends with the block, and a PREFIX filter rejects candidates cheaply. Average about $O(nB/m)$ accesses (no character inside a jump is read), worst case $O(n\sum |P_i|)$, tables of size $O({\sigma }^B)$. Behind agrep (by Wu and Manber), grep -F with many patterns, Snort and antivirus scanners. The shortest pattern rules everything: one 2-character pattern destroys the skipping, so real tools route short patterns to a separate Aho–Corasick pass.

Approach	Representative	Guarantee	When
automaton, left to right	Aho–Corasick	$O(n+\sum |P_i|+occ)$	contests, always: Aho–Corasick
trie + skipping, right to left	Commentz–Walter	none	historical
block hashing + skipping	Wu–Manber	none	long patterns, huge texts
bit-parallel	Bitap variants	$O(n\sum |P_i|/w)$	few short patterns
hashing	multi-pattern Rabin–Karp	$O(n)$ expected	equal-length patterns

// Wu-Manber with block size B = 2 over bytes: all (position, pattern id) occurrences.
vector<pair<int, int>> wuManber(const vector<string>& pats, const string& t) {
    const int B = 2; int m = INT_MAX; for (auto& p : pats) m = min(m, sz(p));
    vector<pair<int, int>> res;
    if (m < B) {                                         // too short to skip: plain search
        for (int id = 0; id < sz(pats); id++) for (size_t pos = t.find(pats[id]); pos != string::npos; pos = t.find(pats[id], pos + 1)) res.push_back({(int)pos, id});
        sort(all(res)); return res;
    }
    auto key = [&](const string& s, int i) { return (unsigned char)s[i - 1] * 256 + (unsigned char)s[i]; };   // block ending at i
    vector<int> shift(1 << 16, m - B + 1); vector<vector<int>> hashTab(1 << 16);
    for (int id = 0; id < sz(pats); id++) {
        for (int i = B - 1; i < m; i++) shift[key(pats[id], i)] = min(shift[key(pats[id], i)], m - 1 - i);
        hashTab[key(pats[id], m - 1)].push_back(id);
    }
    for (int i = m - 1; i < sz(t);) {                    // i = text index of the window's last character
        int k = key(t, i);
        if (shift[k] > 0) { i += shift[k]; continue; }
        int start = i - m + 1;
        for (int id : hashTab[k]) if (t.compare(start, sz(pats[id]), pats[id]) == 0) res.push_back({start, id});
        i++;
    }
    sort(all(res));
    return res;
}

Proof: the Wu–Manber shift is safe, and the Two-Way test

Wu–Manber. An occurrence of pattern $P$ starting at $s$ makes the window ending at $s+m-1$ equal to $P$‘s length-$m$ prefix. If the current window ends at $i$ and an occurrence ends its prefix at $i+d$ with $0\le d$, then the block ending at $i$ is the block of $P$‘s prefix ending at position $m-1-d$, so $d\ge$ the minimum over patterns and positions of $m-1-$ (end position of that block), which is exactly shift. Hence jumping by shift skips no window that could end an occurrence; when the shift is 0 the block ends some pattern’s prefix and all candidates are verified directly. Two-Way. Correctness rests on the critical factorisation theorem (the local period at the critical position equals the global period, so mismatches in the right part allow the shift $t-\ell$ and full matches allow the period shift); the full proof is Crochemore and Perrin’s (1991). Both functions were checked against naive search on random strings over small alphabets (periodic and non-periodic patterns).

Suffix trees. Weiner (1973), “the algorithm of the year” (Knuth): the first linear construction, prepending characters right to left, with per-node tables $I_v[c]$ (does $cv$ occur?) and $A_v[c]$ (the node of $cv$), i.e. reverse suffix links; $O(n\sigma )$ space was the problem. Its view is that of the suffix automaton of the reversed string: the suffix-link tree of the suffix automaton of $\mathrm{reverse}(S)$ is the suffix tree of $S$. McCreight (1976): inserts suffixes from longest to shortest with suffix links (follow the link from the parent of the last leaf instead of restarting) and skip/count (jump whole edges by length, comparing one character per edge); the head/tail bookkeeping ($|{\mathrm{head}}_{i+1}|\ge |{\mathrm{head}}_i|-1$) telescopes to $O(n)$, like Kasai’s LCP; $O(n\log \sigma )$ with balanced children; matching statistics fall out. Ukkonen (1995) is online (left to right). Farach (1997): linear for integer alphabets by odd/even divide and conquer: pair characters, radix sort and rename, recurse on the half-length string to get the odd-suffix tree, derive the even tree in $O(n)$ (one radix sort), then a hard “over-merge” corrected by an amortized argument: $T(n)=T(n/2)+O(n)$. It inspired DC3/skew (thirds instead of halves, an easy merge) and SA-IS (induced sorting replaces the merge). (The same Farach, as Farach-Colton with Bender, gave $O(1)$ RMQ/LCA.) In contests write none of them: a suffix automaton (30 lines) or a suffix array with LCP covers almost every suffix-tree application (Suffix Tree).

Year	Linear suffix structures
1973	Weiner: first linear suffix tree, $O(n\sigma )$ space
1976	McCreight: linear time, $O(n)$ space, offline
1983	Blumer et al.: the DAWG / suffix automaton
1990	Manber–Myers: suffix arrays in $O(n\log n)$, far less memory
1995	Ukkonen: online linear construction
1997	Farach: linear for integer alphabets
2003	Kärkkäinen–Sanders DC3: simple linear suffix array
2009	SA-IS (Nong, Zhang, Chan; after Ko–Aluru): fast linear suffix array, the current standard

Related notes

• Complexity Theory
• Maximum Flow, Minimum Spanning Trees, Lowest Common Ancestor
• FFT, Prefix Function and Z