---
title: "Suffix Arrays, LCP & Aho–Corasick"
module: Sequences & Strings
moduleNumber: 5
lessonNumber: 8
order: 508
summary: |
  A **suffix array** sorts all $n$ suffixes of a string, indexing every substring
  at once; built in $O(n\log n)$, it locates a pattern by binary search in
  $O(m\log n)$. Its companion **LCP array** (Kasai's $O(n)$ algorithm) counts
  distinct substrings and finds the longest repeated substring. **Aho–Corasick**
  generalises KMP to a whole dictionary: a trie of patterns plus failure links
  scans the text once in $O(\text{text} + \text{matches})$ to report every
  occurrence of every pattern. Manacher's algorithm finds all palindromic
  substrings in $O(n)$.
topics: [Strings]
sources:
  - book: CLRS
    ref: "Ch. 32 — String Matching"
  - book: Skiena
    ref: "§ — Suffix Trees and Arrays"
  - book: Erickson
    ref: "Ch. — String Matching"
practice:
  - title: 'Longest Duplicate Substring'
    slug: longest-duplicate-substring
    difficulty: Hard
  - title: 'Stream of Characters'
    slug: stream-of-characters
    difficulty: Hard
  - title: 'Longest Palindromic Substring'
    slug: longest-palindromic-substring
    difficulty: Medium
  - title: 'Count Distinct Substrings (Distinct Echo Substrings)'
    slug: distinct-echo-substrings
    difficulty: Hard
---

The [string-matching lessons](/algorithms/sequences/kmp-and-z-function) matched
_one_ pattern against a text, preprocessing the **pattern**. Two complementary needs remain. The
first is to preprocess the **text** instead, so that afterwards _any_ of many
patterns can be queried fast — exactly the situation of a search engine or a
genome browser, where the text is fixed and the patterns arrive online. The second
is to match _many_ patterns against one text in a single pass. This lesson builds
the two canonical structures for these jobs: the **suffix array** (with its **LCP
array**) for the first, and the **Aho–Corasick automaton** for the second. A short
coda gives **Manacher's** algorithm, which finds every palindrome in linear time by
the same Z-box bookkeeping we have already met.

Both halves keep the [soundness / completeness](/algorithms/foundations/what-is-an-algorithm)
discipline of a matcher: every reported occurrence must be genuine, and every
genuine occurrence must be reported. What changes is _where_ the preprocessing
cost is paid and _what_ a single index then enables.

## Suffix arrays: sorting all the suffixes

Index the text once so that every substring question becomes cheap. A substring of
$T$ is a prefix of some suffix of $T$; if we had all suffixes _in sorted order_,
every occurrence of a pattern $P$ would form a contiguous block (all the suffixes
that start with $P$), findable by binary search. That is the whole idea.

> **Definition (suffix array).** For a string $T[0 \mathinner{\ldotp\ldotp} n-1]$, write $T_i = T[i
> \mathinner{\ldotp\ldotp} n-1]$ for the suffix starting at $i$. The _suffix array_ $\mathit{SA}$ is the
> permutation of $\{0, 1, \dots, n-1\}$ that lists the starting indices of the
> suffixes in lexicographic order:
> $T_{\mathit{SA}[0]} < T_{\mathit{SA}[1]} < \dots < T_{\mathit{SA}[n-1]}$.

It is the array of starting positions, not the suffixes themselves — $O(n)$
integers, where the suffixes laid out in full would be $\Theta(n^2)$ characters.
This compactness is why the suffix array displaced the older **suffix
tree** in practice: same indexing power, a fraction of the memory.[^skiena-sa]

$$
% caption: Suffix array of $T=\texttt{banana}$ with an appended sentinel (smaller than
%          every letter, shown as [end]). Left: all $7$ suffixes. Right: sorted, giving
%          $\mathit{SA}=[6,5,3,1,0,4,2]$. Each row's index is its start position in $T$
\begin{tikzpicture}[font=\small]
  \definecolor{acc}{HTML}{2348F2}
  % unsorted column
  \node[font=\footnotesize] at (0,0.9) {the 7 suf\/f\/ixes of banana};
  \foreach \i/\s in {0/banana,1/anana,2/nana,3/ana,4/na,5/a,6/{[end]}} {
    \node[font=\footnotesize] at (-1.0,{-\i*0.55}) {$\i$};
    \node[anchor=west, font=\ttfamily\footnotesize] at (-0.7,{-\i*0.55}) {\s};
  }
  % arrow
  \draw[->, acc, thick] (2.4,-1.65) -- (3.6,-1.65) node[midway, above, font=\footnotesize, text=acc]{sort};
  % sorted column
  \node[font=\footnotesize, text=acc] at (5.2,0.9) {sorted (SA on left)};
  \foreach \r/\i/\s in {0/6/{[end]},1/5/a,2/3/ana,3/1/anana,4/0/banana,5/4/na,6/2/nana} {
    \node[font=\footnotesize, text=acc] at (4.0,{-\r*0.55}) {\i};
    \node[anchor=west, font=\ttfamily\footnotesize] at (4.3,{-\r*0.55}) {\s};
  }
\end{tikzpicture}
$$

It is convenient to append a sentinel `$` that is smaller than every real
character and occurs nowhere else; it makes every suffix uniquely ordered (no
suffix is a prefix of another) and is shown above as `[end]`.

### Construction by prefix doubling

The naive build — sort the $n$ suffixes with a comparison sort — costs $O(n \log
n)$ comparisons, but each comparison may scan $O(n)$ characters, so $O(n^2 \log
n)$ overall. **Prefix doubling** (the Manber–Myers method) removes the per-compare
blowup by sorting suffixes on growing prefixes of length $1, 2, 4, 8, \dots$,
carrying a _rank_ for each suffix between rounds.

The invariant is that after the round for length $k$, every suffix carries a rank
equal to its position among all suffixes ordered by their first $k$ characters
(ties shared). To go from $k$ to $2k$, sort each suffix $i$ by the **pair**
$\parens{\mathrm{rank}_k[i],\ \mathrm{rank}_k[i+k]}$: the first component orders
by the first $k$ characters, the second breaks ties using the next $k$ — which is
exactly the rank, already computed, of the suffix starting $k$ further along.

> **Lemma (doubling correctness).** After $\lceil \log_2 n \rceil$ rounds every
> suffix has a distinct rank, and that ranking is the lexicographic order of the
> suffixes.

> **Proof.** By induction the round-$k$ rank orders suffixes by their first $k$
> characters. Sorting on $(\mathrm{rank}_k[i], \mathrm{rank}_k[i+k])$ refines this
> to order by the first $2k$ characters, establishing the invariant for $2k$. Once
> $2^r \ge n$, comparing the first $2^r$ characters compares the whole suffix (with
> the sentinel guaranteeing distinctness), so the final ranks are the true
> lexicographic order. $\qed$

$$
% caption: One prefix-doubling round on `banana$`, going from $k=1$ to $k=2$.
%          Each suffix start $i$ carries $\mathrm{rank}_1[i]$ (order by first character) and
%          $\mathrm{rank}_1[i+1]$ (the next character's rank). Sorting suffixes by the pair
%          $(\mathrm{rank}_1[i],\,\mathrm{rank}_1[i+1])$ refines the order to the first $2$
%          characters; the new ranks $\mathrm{rank}_2$ on the right are read off the sorted
%          pairs (equal pairs share a rank). A second component of $-1$ means past the end.
%          Starts $1$ and $3$ tie on the pair $(1,3)$ (both spell `an`), and starts $2$ and
%          $4$ tie on $(3,1)$ (both spell `na`), so each pair shares a rank
\begin{tikzpicture}[font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % header
  \node[text=acc] at (0,0.95) {start};
  \node[text=acc] at (1.4,0.95) {rank here};
  \node[text=acc] at (3.1,0.95) {rank next};
  \draw[draw=acc!40, thick] (-0.7,0.65) -- (3.9,0.65);
  % rank-1 table: i / rank1[i] / rank1[i+1] for banana$ ; ranks a=1 b=2 n=3 sentinel=0
  \foreach \r/\i/\a/\b in {0/0/2/1,1/1/1/3,2/2/3/1,3/3/1/3,4/4/3/1,5/5/1/0,6/6/0/{-1}} {
    \node at (0,{-\r*0.52}) {\i};
    \node[text=acc] at (1.4,{-\r*0.52}) {\a};
    \node[text=acc] at (3.1,{-\r*0.52}) {\b};
  }
  % arrow
  \draw[->, acc, thick] (4.4,-1.56) -- (5.5,-1.56) node[midway, above, text=acc]{sort pairs};
  % sorted-by-pair table on the right: start i / new rank2
  \node[text=acc] at (6.6,0.95) {start};
  \node[text=acc] at (8.4,0.95) {rank};
  \draw[draw=acc!40, thick] (6.2,0.65) -- (8.8,0.65);
  \foreach \r/\i/\nr in {0/6/0,1/5/1,2/1/2,3/3/2,4/0/4,5/4/5,6/2/5} {
    \node at (6.6,{-\r*0.52}) {\i};
    \node[draw=acc, fill=acc!14, minimum size=4.6mm, inner sep=1pt] at (8.4,{-\r*0.52}) {\nr};
  }
\end{tikzpicture}
$$

Run to completion on `banana$`, the build takes two rounds beyond the
initial character ranks. Assigning first-character ranks
(`$` = 0, `a` = 1, `b` = 2, `n` = 3) gives

$$\mathrm{rank}_1 = [\,2,\ 1,\ 3,\ 1,\ 3,\ 1,\ 0\,],$$

with the three `a`-suffixes (starts $1, 3, 5$) tied at rank $1$ and the two
`n`-suffixes (starts $2, 4$) tied at rank $3$. The round above sorts the pairs
$(\mathrm{rank}_1[i], \mathrm{rank}_1[i+1])$ and re-ranks, producing

$$\mathrm{rank}_2 = [\,4,\ 2,\ 5,\ 2,\ 5,\ 1,\ 0\,].$$

Two ties survive: starts $1$ and $3$ still share rank $2$ (both suffixes begin
`an`) and starts $2$ and $4$ share rank $5$ (both begin `na`). The next round
compares two characters further out, i.e. the pairs
$(\mathrm{rank}_2[i], \mathrm{rank}_2[i+2])$. Start $1$ gets the pair
$(2, \mathrm{rank}_2[3]) = (2, 2)$ while start $3$ gets
$(2, \mathrm{rank}_2[5]) = (2, 1)$, so $3$ sorts first: this reproduces the
four-character comparison `ana$` < `anan`, decided by the ranks of
the suffixes two positions along, with no characters rescanned. Likewise start $4$
gets $(5, \mathrm{rank}_2[6]) = (5, 0)$ against start $2$'s
$(5, \mathrm{rank}_2[4]) = (5, 5)$, putting `na$` before `nana$`. The new ranks

$$\mathrm{rank}_4 = [\,4,\ 3,\ 6,\ 2,\ 5,\ 1,\ 0\,]$$

are all distinct, so the loop's early-exit test fires and reading the positions in
rank order yields $\mathit{SA} = [6, 5, 3, 1, 0, 4, 2]$ — the sorted column of the
first figure.

$$
% caption: The complete prefix-doubling trace on `banana$`: one row of ranks per
%          round, one column per start position. Round $k=1$ ranks by single character;
%          each later round refines using the pair $(\mathrm{rank}_k[i], \mathrm{rank}_k[i+k])$.
%          After the $k=2$ round every rank is distinct (green), so sorting the positions by
%          their f\/inal rank reads of\/f the suffix array
\begin{tikzpicture}[font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % header: position index and character
  \node[text=black] at (-1.9,0.62) {i};
  \node[text=black] at (-1.9,0.06) {T[i]};
  \foreach \i/\c in {0/b,1/a,2/n,3/a,4/n,5/a,6/{\char36}} {
    \node[text=black] at ({\i*0.85},0.62) {\i};
    \node[font=\ttfamily\footnotesize] at ({\i*0.85},0.06) {\c};
  }
  \draw[draw=acc!40, thick] (-2.7,-0.26) -- (5.5,-0.26);
  % k = 1 ranks
  \node[text=acc, anchor=west] at (-2.7,-0.72) {k = 1};
  \foreach \i/\v in {0/2,1/1,2/3,3/1,4/3,5/1,6/0} {
    \node at ({\i*0.85},-0.72) {\v};
  }
  \node[text=black, anchor=west] at (5.7,-0.72) {ties remain};
  % k = 2 ranks
  \node[text=acc, anchor=west] at (-2.7,-1.42) {k = 2};
  \foreach \i/\v in {0/4,1/2,2/5,3/2,4/5,5/1,6/0} {
    \node at ({\i*0.85},-1.42) {\v};
  }
  \node[text=black, anchor=west] at (5.7,-1.42) {ties remain};
  % k = 4 ranks: all distinct
  \node[text=acc, anchor=west] at (-2.7,-2.16) {k = 4};
  \foreach \i/\v in {0/4,1/3,2/6,3/2,4/5,5/1,6/0} {
    \node[draw=green, fill=green!8, minimum size=4.6mm, inner sep=1pt] at ({\i*0.85},-2.16) {\v};
  }
  \node[text=green, anchor=west] at (5.7,-2.16) {all distinct};
  % read-off line
  \node[anchor=west, text=acc] at (-2.7,-2.98) {sort positions by f\/inal rank: SA = [6, 5, 3, 1, 0, 4, 2]};
\end{tikzpicture}
$$

The cost accounting: each round sorts $n$ pairs of integers drawn from
$[-1, n)$, which two passes of counting sort (least-significant component first)
do in $O(n)$ time and space; re-ranking is one linear scan of the sorted order.
The prefix length doubles each round, so $\lceil \log_2 n \rceil$ rounds suffice,
and the total is $O(n) \cdot O(\log n) = O(n \log n)$. Swapping the radix sort for
a comparison sort costs $O(n \log n)$ per round instead, giving the
easier-to-code $O(n \log^2 n)$ variant in Algorithm 1. Specialised linear-time
builds exist — the **DC3 / skew** algorithm and **SA-IS** — but doubling is the
standard construction and the one to know.

```algorithm
caption: $\textsc{Build-SA}(T)$ — suffix array by prefix doubling in $O(n\log^2 n)$
number: 1
append sentinel; $n \gets |T|$
$\mathit{rank}[i] \gets T[i]$ for all $i$        // round k = 1: rank by single char
$\mathit{sa} \gets (0, 1, \dots, n-1)$
$k \gets 1$
while $k < n$ do
  define $key(i) = (\mathit{rank}[i],\ \mathit{rank}[i+k]\ \text{or}\ {-}1)$
  sort $\mathit{sa}$ by $key$                    // radix sort for $O(n)$ per round
  $\mathit{tmp}[\mathit{sa}[0]] \gets 0$
  for $p \gets 1$ to $n - 1$ do                  // re-rank, ties keep equal rank
    $\mathit{tmp}[\mathit{sa}[p]] \gets \mathit{tmp}[\mathit{sa}[p-1]]
       + (key(\mathit{sa}[p]) \ne key(\mathit{sa}[p-1])\ ?\ 1 : 0)$
  $\mathit{rank} \gets \mathit{tmp}$
  if $\mathit{rank}[\mathit{sa}[n-1]] = n - 1$ then break   // all ranks distinct
  $k \gets 2k$
return $\mathit{sa}$
```

::impl{algo="suffix_array#build_suffix_array"}

### Pattern matching by binary search

Because the suffixes sit in sorted order, the suffixes that begin with $P$ occupy a
contiguous range of $\mathit{SA}$. Two binary searches — for the lower and upper
bounds of that range — locate every occurrence of $P$.

```algorithm
caption: $\textsc{SA-Search}(T, \mathit{SA}, P)$ — all occurrences of $P$ in $O(m\log n)$
number: 2
$lo \gets 0;\ hi \gets n$                        // find first suffix $\ge P$
while $lo < hi$ do
  $mid \gets (lo + hi) / 2$
  if $T[\mathit{SA}[mid] \mathinner{\ldotp\ldotp}] < P$ then $lo \gets mid + 1$ else $hi \gets mid$
$\mathit{start} \gets lo$
$hi \gets n$                                     // find first suffix $>$ all $P\cdot$
while $lo < hi$ do
  $mid \gets (lo + hi) / 2$
  if $T[\mathit{SA}[mid] \mathinner{\ldotp\ldotp}]$ has prefix $\le P$ then $lo \gets mid + 1$ else $hi \gets mid$
report $\mathit{SA}[\mathit{start} \mathinner{\ldotp\ldotp} lo - 1]$ as the occurrence positions
```

> **Lemma (search cost).** $\textsc{SA-Search}$ finds the occurrence range in
> $O(m \log n)$, and reports $\mathit{occ}$ occurrences in $O(m\log n + \mathit{occ})$.

> **Proof.** Each binary search does $O(\log n)$ iterations; each iteration
> compares $P$ against a suffix prefix, $O(m)$ characters. The range is contiguous
> by sortedness, so the matched indices are read off directly. $\qed$

$$
% caption: Binary search for pattern $P=\texttt{an}$ in the suffix array of $\texttt{banana}$
%          ($\mathit{SA}=[6,5,3,1,0,4,2]$). The suffixes prefixed by `an` (rows $2$ and $3$,
%          starts $3$ and $1$) form one contiguous green block. A probe at the midpoint
%          compares $P$ against that row's suffix and discards the half that cannot contain
%          $P$; two such searches bracket the block's lower and upper ends
\begin{tikzpicture}[font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \node[text=acc] at (-0.9,0.7) {row};
  \node[text=acc] at (0.1,0.7) {SA};
  \node[text=acc] at (1.7,0.7) {suf\/f\/ix};
  \draw[draw=acc!40, thick] (-1.4,0.42) -- (3.4,0.42);
  % the matching contiguous block (rows 2,3) — green = match — drawn first, behind text
  \draw[draw=green, very thick, fill=green!10] (-1.35,{-1.5*0.55}) rectangle (3.35,{-3.5*0.55});
  % non-matching rows (black)
  \foreach \r/\sa/\suf in {0/6/{[end]},1/5/a,4/0/banana,5/4/na,6/2/nana} {
    \node at (-0.9,{-\r*0.55}) {\r};
    \node at (0.1,{-\r*0.55}) {\sa};
    \node[anchor=west, font=\ttfamily\footnotesize] at (0.9,{-\r*0.55}) {\suf};
  }
  % matching rows (green), drawn once
  \foreach \r/\sa/\suf in {2/3/ana,3/1/anana} {
    \node[text=green] at (-0.9,{-\r*0.55}) {\r};
    \node[text=green] at (0.1,{-\r*0.55}) {\sa};
    \node[anchor=west, font=\ttfamily\footnotesize, text=green] at (0.9,{-\r*0.55}) {\suf};
  }
  \node[text=green, anchor=west] at (3.7,{-2.5*0.55}) {blo\/ck for an};
  % a discarded probe (row 5 too large) marked in red — label sits beside its own row
  \draw[->, acc, thick] (5.0,{-5*0.55}) -- (3.5,{-5*0.55});
  \node[text=red, anchor=west, font=\scriptsize] at (5.1,{-5*0.55}) {prob\/e to\/o high};
\end{tikzpicture}
$$

The $\log n$ comparisons each rescanning $m$ characters is the looseness here;
storing the LCP array (next) lets a refined search shave it to $O(m + \log n)$.
**Soundness** holds because a reported index $\mathit{SA}[j]$ lies in the range
only if its suffix has $P$ as a prefix, i.e. $P$ genuinely occurs there;
**completeness** holds because every occurrence is a suffix prefixed by $P$, hence
inside the contiguous range the two searches bracket.

::impl{algo="suffix_array#search"}

## The LCP array: what adjacency reveals

The suffix array alone does not record _how much_ adjacent suffixes share. That
shared length is what substring counting and comparison need.

> **Definition (LCP array).** $\mathit{LCP}[i]$ is the length of the longest common
> prefix of the two suffixes adjacent in sorted order, $T_{\mathit{SA}[i-1]}$ and
> $T_{\mathit{SA}[i]}$, for $i \ge 1$; set $\mathit{LCP}[0] = 0$.

For `banana` with $\mathit{SA} = [6,5,3,1,0,4,2]$ the adjacent pairs share
$\mathit{LCP} = [0,0,1,3,0,0,2]$: e.g. `ana` and `anana` (rows $2$ and $3$) share
the prefix `ana` of length $3$.

$$
% caption: Suffix array and LCP for $T=\texttt{banana}$ (with sentinel). Column SA is the
%          sorted start index; $\mathit{LCP}[i]$ is the longest common prefix of rows $i{-}1$
%          and $i$. The peak $\mathit{LCP}=3$ (highlighted) is `ana`, the longest
%          repeated substring
\begin{tikzpicture}[font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \node[font=\footnotesize] at (-1.0,0.6) {row};
  \node[font=\footnotesize] at (0.2,0.6) {SA};
  \node[font=\footnotesize] at (1.4,0.6) {LCP};
  \node[font=\footnotesize] at (3.4,0.6) {suf\/f\/ix};
  \draw[thick] (-1.6,0.32) -- (5.4,0.32);
  \foreach \r/\sa/\lcp/\suf in {0/6/0/{[end]},1/5/0/a,2/3/1/ana,3/1/3/anana,4/0/0/banana,5/4/0/na,6/2/2/nana} {
    \node[font=\footnotesize] at (-1.0,{-\r*0.55}) {\r};
    \node[font=\footnotesize] at (0.2,{-\r*0.55}) {\sa};
    \node[font=\footnotesize] at (1.4,{-\r*0.55}) {\lcp};
    \node[anchor=west, font=\ttfamily\footnotesize] at (2.3,{-\r*0.55}) {\suf};
  }
  % highlight the peak LCP row (the longest repeat — a match)
  \node[draw=green, very thick, minimum width=7mm, minimum height=5mm, inner sep=0] at (1.4,{-3*0.55}) {};
  \node[font=\footnotesize, text=green, anchor=west] at (4.4,{-3*0.55}) {peak};
\end{tikzpicture}
$$

### Kasai's algorithm: LCP in linear time

A direct LCP computation compares adjacent suffixes character by character,
$O(n^2)$. **Kasai's algorithm** does it in $O(n)$ with one observation: process the
suffixes in the order of the text, $T_0, T_1, T_2, \dots$, and the LCP can drop by
at most one each step, so it never has to be rescanned from scratch.

> **Lemma (Kasai's bound).** If suffix $T_i$ shares $h$ characters with the suffix
> just before it in sorted order, then $T_{i+1}$ shares at least $h - 1$ characters
> with the suffix just before _it_.

> **Proof.** $T_{i+1}$ is $T_i$ with its first character removed. Let $T_j$ be the
> sorted-predecessor of $T_i$ with $\mathrm{lcp}(T_j, T_i) = h \ge 1$. Then
> $T_{j+1}$ (which is $T_j$ minus its first character) shares $h-1$ characters with
> $T_{i+1}$, and $T_{j+1}$ sits somewhere at or before $T_{i+1}$'s predecessor in
> sorted order. Since the immediate predecessor's LCP is the _largest_ among all
> earlier suffixes, $\mathrm{lcp}$ of $T_{i+1}$ with its predecessor is at least
> $h - 1$. $\qed$

So we keep a running match length $h$, start each suffix's comparison from $h - 1$
rather than $0$, and extend. The total of all increments is $O(n)$ because $h$
rises by at most the number of matched characters and falls by at most one per
step.

```algorithm
caption: $\textsc{Kasai}(T, \mathit{SA})$ — LCP array in $O(n)$
number: 3
compute $\mathit{rank}$ as inverse of $\mathit{SA}$   // rank[SA[r]] = r
$h \gets 0$
for $i \gets 0$ to $n - 1$ do                    // suffixes in text order
  if $\mathit{rank}[i] > 0$ then
    $j \gets \mathit{SA}[\mathit{rank}[i] - 1]$    // predecessor in sorted order
    while $i + h < n$ and $j + h < n$ and $T[i+h] = T[j+h]$ do
      $h \gets h + 1$                            // extend the shared prefix
    $\mathit{LCP}[\mathit{rank}[i]] \gets h$
    if $h > 0$ then $h \gets h - 1$              // drop at most one for next suffix
  else
    $h \gets 0$
return $\mathit{LCP}$
```

::impl{algo="kasai_lcp#kasai_lcp"}

### What the LCP array enables

Two classic results fall out immediately.

> **Theorem (longest repeated substring).** The longest substring of $T$ that
> occurs at least twice has length $\max_i \mathit{LCP}[i]$, and the substring
> itself is the corresponding shared prefix.

> **Proof.** A substring repeats iff it is a common prefix of two _different_
> suffixes. Among all pairs of suffixes, the longest common prefix is maximised by
> some _adjacent_ pair in sorted order: if non-adjacent suffixes share $\ell$
> characters, every suffix sorted between them also begins with those same $\ell$
> characters, so an adjacent pair shares at least $\ell$ too. Hence the answer is
> the largest adjacent LCP. $\qed$

For `banana`, $\max \mathit{LCP} = 3$ at the `ana`/`anana` pair, so `ana` is the
longest repeated substring — the basis of _Longest Duplicate Substring_ (which
combines this with binary search on the answer, or a suffix array).

> **Theorem (counting distinct substrings).** The number of distinct non-empty
> substrings of $T$ is
> $$\sum_{i=0}^{n-1} \parens{n - \mathit{SA}[i]} \;-\; \sum_{i=1}^{n-1} \mathit{LCP}[i].$$

> **Proof.** Every substring is a prefix of exactly one suffix; suffix
> $T_{\mathit{SA}[i]}$ contributes $n - \mathit{SA}[i]$ prefixes (its own lengths).
> Summing over all suffixes counts each distinct substring once per suffix it
> prefixes, i.e. with multiplicity. Going down the sorted suffixes, the prefixes of
> $T_{\mathit{SA}[i]}$ that already appeared as prefixes of $T_{\mathit{SA}[i-1]}$
> are precisely its first $\mathit{LCP}[i]$ characters' worth of prefixes; subtracting
> $\mathit{LCP}[i]$ removes precisely those duplicates, leaving each distinct
> substring counted once. $\qed$

The same LCP array also lets a range-minimum query answer the longest-common-prefix
of _any_ two suffixes in $O(1)$ after $O(n)$ preprocessing — the basis of many
competitive-programming string solutions.[^erickson-sa]

::impl{algo="kasai_lcp#longest_repeated_substring+count_distinct_substrings"}

## Aho–Corasick: matching a whole dictionary at once

Now the second job: find every occurrence of _every_ pattern in a set
$\mathcal{P} = \{P_1, \dots, P_k\}$ within a text $T$, in one pass. Running KMP $k$
times costs $O(k \cdot n)$; Aho–Corasick does it in $O(n + z)$ where $z$ is the
total number of matches reported, after $O(\sum |P_i|)$ preprocessing. It is, in
one line, **KMP generalised from a single string to a [trie](/algorithms/sequences/tries)**.

The construction has three layers.

**1. The trie of patterns.** Insert every pattern into a trie (one node per
distinct prefix of some pattern). A node is _terminal_ if its root-path spells a
complete pattern. Following text characters down the `goto` edges of this trie is
exactly the naive idea of matching all patterns simultaneously — until a character
has no outgoing edge, at which point we are stuck.

**2. Failure links.** Just as KMP's $\pi$ jumps, on a mismatch, to the longest
proper prefix of the pattern that is also a suffix of what we matched,
Aho–Corasick's **failure link** $\mathrm{fail}(v)$ points to the node whose
root-path is the **longest proper suffix** of $v$'s root-path that is _also a node
in the trie_ (a prefix of some pattern). When the text has no `goto` edge from the
current node, we follow failure links until an edge exists or we fall back to the
root.

**3. Output links.** A failure link can land on a terminal node, meaning a shorter
pattern ends here too. Following the chain of failure links from any node and
collecting terminals reports every pattern that ends at the current text position;
precomputing these into **output links** makes that enumeration $O(1)$ per reported
match.

$$
% caption: Aho–Corasick automaton for $\mathcal{P}=\{\texttt{he},\texttt{she},
%          \texttt{his},\texttt{hers}\}$. Solid black edges are trie `goto` transitions
%          (labelled by the character); each node shows the pref\/ix it spells. Dashed blue
%          edges are the four failure links that point somewhere other than the root
%          ($\mathrm{fail}(\texttt{sh})=\texttt{h}$, $\mathrm{fail}(\texttt{she})=\texttt{he}$,
%          $\mathrm{fail}(\texttt{his})=\texttt{s}$, $\mathrm{fail}(\texttt{hers})=\texttt{s}$);
%          every omitted failure link points to the root. Green double-ringed nodes are
%          terminal (a pattern ends there)
\begin{tikzpicture}[
  >=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=7.5mm, inner sep=0.5pt, font=\footnotesize},
  term/.style={circle, draw=green, double, double distance=1pt, minimum size=7.5mm, inner sep=0.5pt, font=\footnotesize, text=green},
  edgelbl/.style={draw=none, fill=none, inner sep=2pt},
  fail/.style={draw=acc, thick, dashed, ->}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % states
  \node[st] (r) at (0,0) {};
  \node[draw=none, text=black] at (-0.75,0.3) {root};
  \node[st]   (h)    at (1.7,1.5)  {h};
  \node[term] (he)   at (3.4,2.3)  {he};
  \node[st]   (her)  at (5.1,2.3)  {her};
  \node[term] (hers) at (6.8,2.3)  {hers};
  \node[st]   (hi)   at (3.4,0.7)  {hi};
  \node[term] (his)  at (5.1,0.7)  {his};
  \node[st]   (s)    at (1.7,-1.9) {s};
  \node[st]   (sh)   at (3.4,-1.9) {sh};
  \node[term] (she)  at (5.1,-1.9) {she};
  % goto edges
  \draw[->] (r) -- node[edgelbl, above left] {h} (h);
  \draw[->] (r) -- node[edgelbl, below left] {s} (s);
  \draw[->] (h) -- node[edgelbl, above] {e} (he);
  \draw[->] (h) -- node[edgelbl, below] {i} (hi);
  \draw[->] (he) -- node[edgelbl, above] {r} (her);
  \draw[->] (her) -- node[edgelbl, above] {s} (hers);
  \draw[->] (hi) -- node[edgelbl, above, pos=0.78] {s} (his);
  \draw[->] (s) -- node[edgelbl, above] {h} (sh);
  \draw[->] (sh) -- node[edgelbl, above] {e} (she);
  % failure links (dashed blue): sh->h, she->he, his->s, hers->s
  \draw[fail] (sh) to[bend left=10] (h);
  \draw[fail] (she) -- (he);
  \draw[fail] (his) -- (s);
  \draw[fail] (hers) .. controls (8.0,-0.2) and (5.4,-4.6) .. (s);
\end{tikzpicture}
$$

In the figure, the failure link from `sh` points to `h` (the longest suffix of
`sh` that is a trie node), and from `she` to `he`. The link from `hers` points to
`s`, and `s`'s output chain is empty — but `she`'s failure target `he` is terminal,
so scanning text `…she…` reports both `she` and the embedded `he` at the same
position. That overlap is precisely what output links capture.

$$
% caption: Scanning the text `ushers` through the automaton. The active state walks down
%          `goto` edges spelling `she`; at that terminal it reports `she` and (via its
%          failure target, a terminal) the embedded `he`. Reading the next character `r`,
%          state `she` has no `goto` on `r`, so the scan follows the blue failure link to
%          `he` and continues `he` then `her` then `hers`, reporting `hers` at the end. Green
%          marks the two reported matches; the dashed blue arrow is the failure jump
\begin{tikzpicture}[font=\footnotesize, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % text tape
  \foreach \i/\c in {0/u,1/s,2/h,3/e,4/r,5/s} {
    \node[draw=acc!45, minimum size=6mm, inner sep=0, font=\ttfamily] (tape\i) at ({\i*0.9},2.2) {\c};
  }
  % states visited, laid left to right
  \node[draw, circle, minimum size=6mm, inner sep=0] (s) at (0,0.6) {s};
  \node[draw, circle, minimum size=6mm, inner sep=0] (sh) at (1.5,0.6) {sh};
  \node[draw=green, double, double distance=1pt, circle, minimum size=6mm, inner sep=0, text=green] (she) at (3.0,0.6) {she};
  \node[draw=green, double, double distance=1pt, circle, minimum size=6mm, inner sep=0, text=green] (he) at (3.0,-1.2) {he};
  \node[draw, circle, minimum size=6mm, inner sep=0] (her) at (4.6,-1.2) {her};
  \node[draw=green, double, double distance=1pt, circle, minimum size=6mm, inner sep=0, text=green] (hers) at (6.2,-1.2) {hers};
  % goto walk
  \draw[->, thick] (s) -- node[above, font=\scriptsize]{h} (sh);
  \draw[->, thick] (sh) -- node[above, font=\scriptsize]{e} (she);
  % failure jump she -> he (no goto on r)
  \draw[->, acc, dashed, thick] (she) -- node[right, text=acc, font=\scriptsize]{fail} (he);
  % continue on r then s
  \draw[->, thick] (he) -- node[above, font=\scriptsize]{r} (her);
  \draw[->, thick] (her) -- node[above, font=\scriptsize]{s} (hers);
  % report labels
  \node[text=green, font=\scriptsize, anchor=west] at (3.5,0.6) {rep\/ort she and he};
  \node[text=green, font=\scriptsize, anchor=west] at (6.7,-1.2) {rep\/ort hers};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Build-AC}(\mathcal{P})$ — trie + failure/output links via BFS in $O(\sum|P_i|)$
number: 4
build trie of all patterns; mark terminal nodes
$\mathrm{fail}(root) \gets root$
$Q \gets$ empty queue
for each child $c$ of $root$ do                 // depth-1 nodes fail to root
  $\mathrm{fail}(c) \gets root;\ $ enqueue $c$
while $Q$ nonempty do
  $u \gets$ dequeue
  for each labelled edge $u \xrightarrow{a} v$ do
    enqueue $v$
    $f \gets \mathrm{fail}(u)$
    while $f \ne root$ and $f$ has no edge on $a$ do
      $f \gets \mathrm{fail}(f)$                 // climb failure links, like KMP
    $\mathrm{fail}(v) \gets$ ($f$ has edge on $a$ and that target $\ne v$) ? target : $root$
    $\mathrm{out}(v) \gets \mathrm{out}(\mathrm{fail}(v))$ plus ($v$ terminal ? $v$ : none)
```

```algorithm
caption: $\textsc{AC-Scan}(T)$ — report all occurrences of all patterns in $O(n + z)$
number: 5
$x \gets root$
for $i \gets 0$ to $n - 1$ do
  while $x \ne root$ and $x$ has no edge on $T[i]$ do
    $x \gets \mathrm{fail}(x)$                   // no goto: follow failure links
  if $x$ has edge on $T[i]$ then $x \gets$ that target
  for each pattern $P$ in $\mathrm{out}(x)$ do
    report $P$ ending at position $i$
```

> **Theorem (Aho–Corasick correctness and cost).** $\textsc{AC-Scan}$ reports every
> occurrence of every pattern, and only genuine occurrences, in $O(n + z)$ time
> after $O(\sum |P_i|)$ preprocessing, where $z$ is the number of reported matches.

> **Proof.** _Invariant:_ after reading $T[0 \mathinner{\ldotp\ldotp} i]$, the active node $x$ is the
> trie node whose root-path is the **longest suffix** of $T[0 \mathinner{\ldotp\ldotp} i]$ that is a
> prefix of some pattern. The failure-link climb maintains this exactly as KMP's
> $\pi$ does for one pattern. _Completeness:_ a pattern $P_j$ ends at $i$ iff $P_j$
> is a suffix of $T[0 \mathinner{\ldotp\ldotp} i]$; then $P_j$'s node lies on the failure-link chain
> from $x$, hence in $\mathrm{out}(x)$, so it is reported. _Soundness:_ every node
> in $\mathrm{out}(x)$ is terminal with root-path a suffix of $T[0\mathinner{\ldotp\ldotp} i]$, i.e. a
> genuine occurrence. _Cost:_ the scan's node pointer behaves like KMP's $q$ — it
> advances at most $n$ times and the total failure-link descents are bounded by the
> advances, so $O(n)$; each reported match is $O(1)$ via output links, adding $z$.
> Preprocessing is one BFS over $\sum |P_i|$ nodes. $\qed$

The structure is the same soundness-in-verification, completeness-in-coverage split
we saw for single-pattern matching, now carried by the automaton's links rather
than a single array. Aho–Corasick underlies dictionary scanners,
intrusion-detection signature matching, and LeetCode's _Stream of Characters_
(reverse the patterns and feed the stream backward into the automaton).[^clrs-ac]

::impl{algo="aho_corasick"}

> **Remark (a deterministic automaton).** Replacing each on-the-fly failure climb
> with a precomputed transition $\delta(x, a)$ for every state $x$ and character
> $a$ turns the structure into a genuine DFA: the scan then does one table lookup
> per text character, a strict $O(n + z)$ with no inner loop, at the cost of an
> $O(|\text{states}| \cdot |\Sigma|)$ transition table. This is the exact analogue
> of compiling KMP's $\pi$ into a string-matching automaton.

## Manacher's algorithm: all palindromes in $O(n)$

A short coda on a third linear-time string algorithm, included because it reuses the
**Z-box** idea from the [Z-function lesson](/algorithms/sequences/kmp-and-z-function) almost
verbatim. We want, for each centre, the radius of the longest palindrome centred
there — which yields the longest palindromic substring and, summed, the count of
all palindromic substrings.

To unify odd- and even-length palindromes, interleave a
separator: transform $T = \texttt{aba}$ into $S = \texttt{|a|b|a|}$ (with distinct end
sentinels at both ends), so every palindrome of $S$ has odd length and a real centre.
Then compute $\mathit{rad}[c]$,
the palindromic radius at each centre $c$ of $S$.

The linear-time computation maintains the rightmost palindrome found so far, by
centre $C$ and right edge $R$ (exactly the Z-box, now centred). For a new centre
$c < R$, its mirror $c_m = 2C - c$ gives a free lower bound $\mathit{rad}[c] \gets
\min(\mathit{rad}[c_m],\ R - c)$; then extend past $R$ by direct comparison and slide
$(C, R)$ if the new palindrome reaches further right.

$$
% caption: Manacher mirror step. The palindrome centred at $C$ reaches right edge $R$;
%          a new centre $c$ inside it copies its mirror $c_m=2C-c$, giving the free bound
%          $\mathit{rad}[c]\gets\min(\mathit{rad}[c'],\,R-c)$ before extending past $R$
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \draw[thick] (0,0) -- (10,0);
  % big palindrome span around C (the known palindrome) — plain structure
  \draw[very thick] (1.2,0.05) -- (8.8,0.05);
  \node[font=\footnotesize] at (1.2,0.4) {$L$};
  \node[font=\footnotesize] at (8.8,0.4) {$R$};
  \node[circle, fill=black, inner sep=1.6pt] at (5,0) {};
  \node[font=\footnotesize] at (5,-0.42) {$C$};
  % mirror c' and c — distinguishable blue tint (lighter, ringed)
  \node[circle, draw=acc, fill=acc!22, thick, inner sep=1.8pt] at (3.4,0) {};
  \node[font=\footnotesize, text=acc] at (3.4,0.4) {$c_m$};
  \node[circle, draw=acc, fill=acc!22, thick, inner sep=1.8pt] at (6.6,0) {};
  \node[font=\footnotesize, text=acc] at (6.6,0.4) {$c$};
  \draw[acc, dashed, ->] (3.4,-0.5) .. controls (4.2,-1.1) and (5.8,-1.1) .. (6.6,-0.5);
  \node[font=\footnotesize, text=acc] at (5,-1.35) {copy radius};
\end{tikzpicture}
$$

$$
% caption: Expanding a palindrome at centre $c$ on the transformed string
%          $S=\texttt{|a|b|a|}$. Starting from the mirror bound, the radius grows while the
%          characters at $c-r-1$ and $c+r+1$ match (green pairs); it stops at the first
%          mismatch (red pair). The final radius $\mathit{rad}[c]$ is the count of matched
%          steps; if $c+\mathit{rad}[c]$ passes the old right edge, $(C,R)$ advances to here
\begin{tikzpicture}[font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % S = sep a sep b sep a sep  with a mismatch beyond — use a longer illustrative tape
  \foreach \i/\c in {1/a,3/b,5/a} {
    \node[draw, minimum size=6mm, inner sep=0, font=\ttfamily] (m\i) at ({\i*0.95},0) {\c};
  }
  % separator cells: drawn vertical bar instead of a text glyph
  \foreach \i in {0,2,4,6} {
    \node[draw, minimum size=6mm, inner sep=0] (m\i) at ({\i*0.95},0) {};
    \draw[black, line width=0.7pt] ({\i*0.95},-0.14) -- ({\i*0.95},0.14);
  }
  % centre at index 3 (the b)
  \node[text=acc, font=\scriptsize] at ({3*0.95},0.55) {centre};
  \draw[->, acc] ({3*0.95},0.45) -- ({3*0.95},0.2);
  % matched pair r=1: index 2 and 4 (sep and sep) — green
  \draw[green, thick] ({2*0.95},-0.45) -- ({2*0.95},-0.3);
  \draw[green, thick] ({4*0.95},-0.45) -- ({4*0.95},-0.3);
  \draw[green, thick, <->] ({2*0.95},-0.55) to[bend right=18] ({4*0.95},-0.55);
  \node[text=green, font=\scriptsize] at ({3*0.95},-0.95) {mat\/ch};
  % matched pair r=2: index 1 and 5 (a and a) — green
  \draw[green, thick, <->] ({1*0.95},-1.15) to[bend right=14] ({5*0.95},-1.15);
  \node[text=green, font=\scriptsize] at ({3*0.95},-1.55) {mat\/ch};
  % mismatch pair r=3: index 0 and 6 (sep and sep) here actually match at ends — use red label for stop at boundary
  \draw[red, thick, <->] ({0*0.95},-1.75) to[bend right=11] ({6*0.95},-1.75);
  \node[text=red, font=\scriptsize] at ({3*0.95},-2.15) {stop at end};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Manacher}(T)$ — radius of the longest palindrome at every centre in $O(n)$
number: 6
$S \gets$ interleave $T$ with separators and end sentinels
$C \gets 0;\ R \gets 0$
for $c \gets 1$ to $|S| - 2$ do
  if $c < R$ then
    $\mathit{rad}[c] \gets \min(R - c,\ \mathit{rad}[2C - c])$   // mirror bound
  while $S[c + \mathit{rad}[c] + 1] = S[c - \mathit{rad}[c] - 1]$ do
    $\mathit{rad}[c] \gets \mathit{rad}[c] + 1$                  // extend past $R$
  if $c + \mathit{rad}[c] > R$ then
    $C \gets c;\ R \gets c + \mathit{rad}[c]$                    // advance the box
return $\mathit{rad}$
```

Each character is examined a constant number of times because $R$ only ever moves
right, monotonically from $0$ to $|S|$ — the identical amortised argument as the
Z-function. The longest palindromic substring is the centre of maximum radius
($\max_c \mathit{rad}[c]$), and $\sum_c \lceil \mathit{rad}[c] / 1 \rceil$ over real
centres counts all palindromic substrings, both in $O(n)$.

::impl{algo="manacher"}

## Linear construction, bioinformatics, and self-indexes

Suffix arrays became practical when Manber and Myers (_Suffix Arrays: A New
Method for On-Line String Searches_, SIAM J. Comput. 1993) introduced them
explicitly as a space-frugal replacement for suffix trees, and the theory
sharpened further when Kärkkäinen and Sanders gave the **DC3 (skew)
algorithm** (_Simple Linear Work Suffix Array Construction_, ICALP 2003), which
builds the suffix array in genuine $O(n)$ time by a divide step that sorts two
thirds of the suffixes recursively and merges in the rest. The $O(n \log n)$
prefix-doubling method in this lesson is the one most people implement, but the
existence of linear-time construction is what lets suffix arrays index
gigabyte-scale texts.

The reason suffix arrays matter far beyond exercises is **bioinformatics** and
**compression**. The Burrows–Wheeler transform (Burrows & Wheeler, _A Block-
Sorting Lossless Data Compression Algorithm_, 1994) is a permutation of the text
read directly off the sorted suffixes, and it is the basis of the `bzip2`
compressor; layered with the suffix array's rank information it becomes the **FM-
index** (Ferragina & Manzini, _Opportunistic Data Structures with Applications_,
FOCS 2000), a self-index that searches a compressed text without decompressing
it. Genome aligners such as `bwa` and `bowtie` are FM-indexes over a reference
genome — the same suffix-array machinery, made succinct.

Aho–Corasick, for its part, is the multi-pattern matcher (Aho & Corasick,
_Efficient String Matching: An Aid to Bibliographic Search_, CACM 1975) inside
classical tools like `fgrep` and inside intrusion-detection systems such as
Snort, which must scan every packet against thousands of signatures at once —
precisely the failure-automaton-on-a-trie construction this lesson builds.
Manacher's algorithm (Manacher, 1975) rounds out the trio as the linear-time
palindrome scanner, and all three share the amortised "a pointer only moves
right" argument that runs through this entire module.

## Takeaways

- A **suffix array** $\mathit{SA}$ lists the start indices of all $n$ suffixes in
  sorted order — $O(n)$ integers indexing every substring. **Prefix doubling**
  builds it in $O(n\log n)$ (or $O(n\log^2 n)$ with a comparison sort); pattern
  search is two binary searches in $O(m\log n)$, since occurrences form a
  contiguous range.
- The **LCP array** records the shared prefix length of sorted-adjacent suffixes,
  computable in $O(n)$ by **Kasai's algorithm** (the running match drops by at most
  one per text-order step). It gives the **longest repeated substring**
  ($\max_i \mathit{LCP}[i]$) and the **count of distinct substrings**
  ($\sum (n - \mathit{SA}[i]) - \sum \mathit{LCP}[i]$).
- **Aho–Corasick** is **KMP on a trie**: a trie of all patterns plus **failure
  links** (longest proper-suffix node) and **output links** (chained terminals)
  scans the text once in $O(n + z)$, reporting every occurrence of every pattern.
  Soundness lives in the terminal output, completeness in the failure-link
  invariant; precompiling transitions yields a true DFA.
- **Manacher's algorithm** finds the palindromic radius at every centre in $O(n)$
  by the **Z-box** mirror-and-extend trick on a separator-interleaved string,
  giving the longest palindromic substring and the count of all palindromes.

[^skiena-sa]: **Skiena**, § — Suffix Trees and Arrays: suffix arrays as the space-efficient successor to suffix trees, with binary-search substring queries.
[^erickson-sa]: **Erickson**, Ch. — String Matching: the LCP array, Kasai's linear-time construction, and the distinct-substring and longest-repeat corollaries.
[^clrs-ac]: **CLRS**, Ch. 32 — String Matching (§32.3–32.4): finite-automaton matching and the failure-function machinery that Aho–Corasick generalises from one pattern to a dictionary.