Suffix Arrays, LCP & Aho–Corasick

The string-matching lessons 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 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.

It is the array of starting positions, not the suffixes themselves — $O (n)$ integers, where the suffixes laid out in full would be $Θ (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.¹

Suffix array of

T = banana

with an appended sentinel (smaller than every letter, shown as [end]). Left: all

7

suffixes. Right: sorted, giving

SA = [6, 5, 3, 1, 0, 4, 2]

. Each row's index is its start position in

T

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 $2 k$ , sort each suffix $i$ by the pair $(rank_{k} [i], 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.

One prefix-doubling round on

banana $‘, g o in g f r o m$ k=1 $t o$ k=2 $. E a c h s u f f i x s t a r t$ i $c a r r i es$ \mathrm{rank}_1[i] $(or d er b y f i r s t c ha r a c t er) an d$ \mathrm{rank}_1[i+1] $(t h e n e x t c ha r a c t e r^{'} sr ank) . S or t in g s u f f i x es b y t h e p ai r$ (\mathrm{rank}_1[i],\,\mathrm{rank}_1[i+1]) $r e f in es t h eor d er t o t h e f i r s t$ 2 $c ha r a c t er s; t h e n e w r ank s$ \mathrm{rank}_2 $o n t h er i g h t a r er e a d o f f t h esor t e d p ai r s (e q u a l p ai r ss ha r e a r ank) . A seco n d co m p o n e n t o f$ -1 $m e an s p a s tt h ee n d . S t a r t s$ 1 $an d$ 3 $t i eo n t h e p ai r$ (1,3) $(b o t h s p e l l ‘ an ‘), an d s t a r t s$ 2 $an d$ 4 $t i eo n$ (3,1)$ (both spell

na`), so each pair shares a rank

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

$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 $(rank_{1} [i], rank_{1} [i + 1])$ and re-ranks, producing

$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 $(rank_{2} [i], rank_{2} [i + 2])$ . Start $1$ gets the pair $(2, rank_{2} [3]) = (2, 2)$ while start $3$ gets $(2, 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, rank_{2} [6]) = (5, 0)$ against start $2$ 's $(5, rank_{2} [4]) = (5, 5)$ , putting na$ before nana$. The new ranks

$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 $SA = [6, 5, 3, 1, 0, 4, 2]$ — the sorted column of the first figure.

The complete prefix-doubling trace on `banana

‘ : o n er o w o f r ank s p er r o u n d, o n eco l u mn p er s t a r tp os i t i o n . R o u n d

k=1

r ank s b y s in g l ec ha r a c t er; e a c h l a t er r o u n d r e f in es u s in g t h e p ai r

(\mathrm{rank}_k[i], \mathrm{rank}_k[i+k])

. A f t er t h e

k=2$ round every rank is distinct (green), so sorting the positions by their f/inal rank reads of/f the suffix array

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 $⌈ log_{2} n ⌉$ 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 1:

\textsc{Build-SA}(T)

— suffix array by prefix doubling in

O(n\log^2 n)

1
append sentinel; $n \gets |T|$
2
$\mathit{rank}[i] \gets T[i]$ for all $i$
round k = 1: rank by single char
3
$\mathit{sa} \gets (0, 1, \dots, n-1)$
4
$k \gets 1$
5
while $k < n$ do
6
define $key(i) = (\mathit{rank}[i],\ \mathit{rank}[i+k]\ \text{or}\ {-}1)$
7
sort $\mathit{sa}$ by $key$
radix sort for $O(n)$ per round
8
$\mathit{tmp}[\mathit{sa}[0]] \gets 0$
9
for $p \gets 1$ to $n - 1$ do
re-rank, ties keep equal rank
10
$\mathit{tmp}[\mathit{sa}[p]] \gets \mathit{tmp}[\mathit{sa}[p-1]]
11
+ (key(\mathit{sa}[p]) \ne key(\mathit{sa}[p-1])\ ?\ 1 : 0)$
12
$\mathit{rank} \gets \mathit{tmp}$
13
if $\mathit{rank}[\mathit{sa}[n-1]] = n - 1$ then break
all ranks distinct
14
$k \gets 2k$
15
return $\mathit{sa}$

suffix_array.pypython

def build_suffix_array(text: str) -> list[int]:
  """
    The suffix array of `text`: a permutation of 0..n-1 listing suffix start\n
    indices in lexicographic order. Built by prefix doubling.\n
    The empty string yields the empty array.\n
  """
  length: int = len(text)
  if length == 0:
    return []

  # round k = 1: rank each suffix by its single starting character.
  ranks: list[int] = [ord(character) for character in text]
  suffix_array: list[int] = list(range(length))
  temporary: list[int] = [0 for _ in range(length)]

  span: int = 1
  while span < length:

    # key orders by the first `span` chars, breaking ties by the next `span`
    # (the rank, already computed, of the suffix `span` further along; -1 past
    # the end so a shorter suffix sorts before a longer one sharing a prefix).
    def key(start: int) -> tuple[int, int]:
      second: int = ranks[start + span] if start + span < length else -1
      return (ranks[start], second)

    suffix_array.sort(key=key)

    # re-rank the sorted suffixes; equal keys keep an equal rank.
    temporary[suffix_array[0]] = 0
    for position in range(1, length):
      previous_start: int = suffix_array[position - 1]
      current_start: int = suffix_array[position]
      step: int = 1 if key(current_start) != key(previous_start) else 0
      temporary[current_start] = temporary[previous_start] + step
    ranks = temporary[:]

    # once every rank is distinct the order is final; else double the prefix.
    if ranks[suffix_array[-1]] == length - 1:
      break
    span *= 2

  return 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 $SA$ . Two binary searches — for the lower and upper bounds of that range — locate every occurrence of $P$ .

Algorithm 2:

\textsc{SA-Search}(T, \mathit{SA}, P)

— all occurrences of

P

O(m\log n)

1
$lo \gets 0;\ hi \gets n$
find first suffix $\ge P$
2
while $lo < hi$ do
3
$mid \gets (lo + hi) / 2$
4
if $T[\mathit{SA}[mid] \mathinner{\ldotp\ldotp}] < P$ then $lo \gets mid + 1$ else $hi \gets mid$
5
$\mathit{start} \gets lo$
6
$hi \gets n$
find first suffix $>$ all $P\cdot$
7
while $lo < hi$ do
8
$mid \gets (lo + hi) / 2$
9
if $T[\mathit{SA}[mid] \mathinner{\ldotp\ldotp}]$ has prefix $\le P$ then $lo \gets mid + 1$ else $hi \gets mid$
10
report $\mathit{SA}[\mathit{start} \mathinner{\ldotp\ldotp} lo - 1]$ as the occurrence positions

Binary search for pattern

P = an

in the suffix array of

banana

(

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

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 $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.

suffix_array.pypython

def _suffix_compare_pattern(text: str, start: int, pattern: str) -> int:
  """
    Compare the suffix `text[start:]` against `pattern` over the pattern's\n
    length: -1 if the suffix sorts before `pattern`, +1 if after, 0 if the\n
    suffix has `pattern` as a prefix.\n
  """
  text_length: int = len(text)
  for offset in range(len(pattern)):
    position: int = start + offset
    if position >= text_length:

      # suffix ran out: it is a proper prefix of `pattern`, hence smaller.
      return -1
    if text[position] < pattern[offset]:
      return -1
    if text[position] > pattern[offset]:
      return 1
  return 0


def search(text: str, suffix_array: list[int], pattern: str) -> list[int]:
  """
    Every start position in `text` where `pattern` occurs, in increasing\n
    order. Two binary searches bracket the contiguous block of suffixes\n
    prefixed by `pattern`. The empty pattern matches at every position.\n
  """
  length: int = len(suffix_array)
  if pattern == "":
    return list(range(len(text) + 1)) if text == "" else list(range(len(text)))

  # lower bound: first suffix that is not smaller than `pattern`.
  low: int = 0
  high: int = length
  while low < high:
    middle: int = (low + high) // 2
    if _suffix_compare_pattern(text, suffix_array[middle], pattern) < 0:
      low = middle + 1
    else:
      high = middle
  first: int = low

  # upper bound: first suffix that is strictly greater (not prefixed by it).
  high = length
  while low < high:
    middle = (low + high) // 2
    if _suffix_compare_pattern(text, suffix_array[middle], pattern) <= 0:
      low = middle + 1
    else:
      high = middle

  positions: list[int] = sorted(suffix_array[index] for index in range(first, low))
  return positions

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.

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

Suffix array and LCP for

T = banana

(with sentinel). Column SA is the sorted start index;

LCP [i]

is the longest common prefix of rows

i - 1

and

i

. The peak

LCP = 3

(highlighted) is ana, the longest repeated substring

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.

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 3:

\textsc{Kasai}(T, \mathit{SA})

— LCP array in

O(n)

1
compute $\mathit{rank}$ as inverse of $\mathit{SA}$
rank[SA[r]] = r
2
$h \gets 0$
3
for $i \gets 0$ to $n - 1$ do
suffixes in text order
4
if $\mathit{rank}[i] > 0$ then
5
$j \gets \mathit{SA}[\mathit{rank}[i] - 1]$
predecessor in sorted order
6
while $i + h < n$ and $j + h < n$ and $T[i+h] = T[j+h]$ do
7
$h \gets h + 1$
extend the shared prefix
8
$\mathit{LCP}[\mathit{rank}[i]] \gets h$
9
if $h > 0$ then $h \gets h - 1$
drop at most one for next suffix
10
else
11
$h \gets 0$
12
return $\mathit{LCP}$

kasai_lcp.pypython

def kasai_lcp(text: str, suffix_array: list[int]) -> list[int]:
  """
    The LCP array of `text` given its `suffix_array`, by Kasai's algorithm.\n
    LCP[0] is 0; LCP[i] for i >= 1 is the longest common prefix length of the\n
    suffixes at sorted ranks i-1 and i. Runs in O(n).\n
  """
  length: int = len(text)
  if length == 0:
    return []

  # rank is the inverse permutation: rank[start] is that suffix's sorted row.
  rank: list[int] = [0 for _ in range(length)]
  for sorted_row, start in enumerate(suffix_array):
    rank[start] = sorted_row

  # walk suffixes in text order; the match length only ever drops by one.
  longest_common_prefix: list[int] = [0 for _ in range(length)]
  match_length: int = 0
  for start in range(length):
    if rank[start] == 0:
      match_length = 0
      continue

    # extend the shared prefix with the predecessor from the inherited length.
    predecessor_start: int = suffix_array[rank[start] - 1]
    while (
      start + match_length < length
      and predecessor_start + match_length < length
      and text[start + match_length] == text[predecessor_start + match_length]
    ):
      match_length += 1

    # record it, then surrender one character for the next text-order suffix.
    longest_common_prefix[rank[start]] = match_length
    if match_length > 0:
      match_length -= 1

  return longest_common_prefix

What the LCP array enables

Two classic results fall out immediately.

For banana, $max 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).

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.²

kasai_lcp.pypython

def longest_repeated_substring(
  text: str, suffix_array: list[int], longest_common_prefix: list[int]
) -> str:
  """
    The longest substring of `text` that occurs at least twice, taken as the\n
    shared prefix at the peak of the LCP array. Empty if no substring repeats.\n
    Ties pick the first peak encountered.\n
  """
  if not longest_common_prefix:
    return ""

  # the peak of the LCP array is the longest prefix two suffixes share.
  best_length: int = 0
  best_row: int = 0
  for row in range(1, len(longest_common_prefix)):
    if longest_common_prefix[row] > best_length:
      best_length = longest_common_prefix[row]
      best_row = row

  if best_length == 0:
    return ""

  start: int = suffix_array[best_row]
  return text[start : start + best_length]


def count_distinct_substrings(
  text: str, suffix_array: list[int], longest_common_prefix: list[int]
) -> int:
  """
    The number of distinct non-empty substrings of `text`, computed as\n
    sum(n - SA[i]) - sum(LCP[i]). Each suffix contributes its own prefixes;\n
    the LCP subtraction removes those already seen in the sorted order.\n
  """
  length: int = len(text)
  total_prefixes: int = sum(length - start for start in suffix_array)
  shared_prefixes: int = sum(longest_common_prefix)
  return total_prefixes - shared_prefixes

Aho–Corasick: matching a whole dictionary at once

Now the second job: find every occurrence of every pattern in a set $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.

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 $π$ 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 $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.

Aho–Corasick automaton for

P = {he, she, his, 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 (

fail (sh) = h

fail (she) = he

fail (his) = s

fail (hers) = s

); every omitted failure link points to the root. Green double-ringed nodes are terminal (a pattern ends there)

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.

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

Algorithm 4:

\textsc{Build-AC}(\mathcal{P})

— trie + failure/output links via BFS in

O(\sum|P_i|)

1
build trie of all patterns; mark terminal nodes
2
$\mathrm{fail}(root) \gets root$
3
$Q \gets$ empty queue
4
for each child $c$ of $root$ do
depth-1 nodes fail to root
5
$\mathrm{fail}(c) \gets root;\$ enqueue $c$
6
while $Q$ nonempty do
7
$u \gets$ dequeue
8
for each labelled edge $u \xrightarrow{a} v$ do
9
enqueue $v$
10
$f \gets \mathrm{fail}(u)$
11
while $f \ne root$ and $f$ has no edge on $a$ do
12
$f \gets \mathrm{fail}(f)$
climb failure links, like KMP
13
$\mathrm{fail}(v) \gets$ ( $f$ has edge on $a$ and that target $\ne v$ ) ? target : $root$
14
$\mathrm{out}(v) \gets \mathrm{out}(\mathrm{fail}(v))$ plus ( $v$ terminal ? $v$ : none)

Algorithm 5:

\textsc{AC-Scan}(T)

— report all occurrences of all patterns in

O(n + z)

1
$x \gets root$
2
for $i \gets 0$ to $n - 1$ do
3
while $x \ne root$ and $x$ has no edge on $T[i]$ do
4
$x \gets \mathrm{fail}(x)$
no goto: follow failure links
5
if $x$ has edge on $T[i]$ then $x \gets$ that target
6
for each pattern $P$ in $\mathrm{out}(x)$ do
7
report $P$ ending at position $i$

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).³

aho_corasick.pypython

from collections import deque
from collections.abc import Iterable, Iterator
from typing import NamedTuple, Optional

class Match(NamedTuple):
  """
    One reported occurrence: the pattern and the end position in the text\n
    where it finishes (the index of its last character).\n
  """
  pattern: str
  end: int

class AhoCorasickNode:
  """
    A single automaton node: child `goto` links keyed by character, a failure\n
    link to the longest-proper-suffix node, an output link to the nearest\n
    terminal up the failure chain, and the pattern ending here (if any).\n
  """

  def __init__(self) -> None:
    self.children: dict[str, AhoCorasickNode] = {}
    self.failure: Optional[AhoCorasickNode] = None
    self.output: Optional[AhoCorasickNode] = None
    self.pattern: Optional[str] = None

class AhoCorasick:
  """
    A dictionary-matching automaton over a fixed set of patterns.\n
  """

  def __init__(self, patterns: Iterable[str]) -> None:
    """
      Build the trie of `patterns`, then wire failure and output links by a\n
      breadth-first sweep. Empty patterns are ignored.\n
    """
    self.root: AhoCorasickNode = AhoCorasickNode()
    for pattern in patterns:
      if pattern:
        self._insert(pattern)
    self._build_links()

  def _insert(self, pattern: str) -> None:
    """
      Add `pattern` to the trie, marking its terminal node.\n
    """
    node: AhoCorasickNode = self.root
    for character in pattern:
      node = node.children.setdefault(character, AhoCorasickNode())
    node.pattern = pattern

  def _build_links(self) -> None:
    """
      Compute failure and output links by BFS over the trie. A node's failure\n
      target is found by climbing its parent's failure chain until an edge on\n
      the same character exists; its output link points at the failure target\n
      if that is terminal, else inherits the target's output link.\n
    """
    self.root.failure = self.root
    queue: deque[AhoCorasickNode] = deque()

    # depth-1 nodes fail to the root.
    for child in self.root.children.values():
      child.failure = self.root
      queue.append(child)

    while queue:
      node: AhoCorasickNode = queue.popleft()
      for character, target in node.children.items():
        queue.append(target)

        # climb failure links from the parent until an edge on `character`.
        fallback: AhoCorasickNode = node.failure if node.failure else self.root
        while fallback is not self.root and character not in fallback.children:
          fallback = fallback.failure if fallback.failure else self.root

        # the edge target there is the failure link, unless it loops to itself.
        candidate: Optional[AhoCorasickNode] = fallback.children.get(character)
        target.failure = (
          candidate if candidate is not None and candidate is not target else self.root
        )

        # output: nearest terminal at or above the failure target.
        failure_node: AhoCorasickNode = target.failure
        if failure_node.pattern is not None:
          target.output = failure_node
        else:
          target.output = failure_node.output

  def _advance(self, node: AhoCorasickNode, character: str) -> AhoCorasickNode:
    """
      The state reached from `node` on `character`: follow the edge if it\n
      exists, otherwise climb failure links until one does or fall to root.\n
    """
    current: AhoCorasickNode = node
    while current is not self.root and character not in current.children:
      current = current.failure if current.failure else self.root
    return current.children.get(character, self.root)

  def search(self, text: str) -> Iterator[Match]:
    """
      Yield a `Match` for every occurrence of every pattern in `text`, in\n
      order of end position. A position may report several patterns when one\n
      pattern is a suffix of another's match.\n
    """
    node: AhoCorasickNode = self.root
    for position, character in enumerate(text):
      node = self._advance(node, character)

      # report the pattern ending here, if any.
      if node.pattern is not None:
        yield Match(node.pattern, position)

      # then chase output links for any shorter patterns ending here too.
      output_node: Optional[AhoCorasickNode] = node.output
      while output_node is not None:
        if output_node.pattern is not None:
          yield Match(output_node.pattern, position)
        output_node = output_node.output

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 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 = aba$ into $S = |a|b|a|$ (with distinct end sentinels at both ends), so every palindrome of $S$ has odd length and a real centre. Then compute $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} = 2 C - c$ gives a free lower bound $rad [c] \leftarrow min (rad [c_{m}], R - c)$ ; then extend past $R$ by direct comparison and slide $(C, R)$ if the new palindrome reaches further right.

Manacher mirror step. The palindrome centred at

C

reaches right edge

R

; a new centre

c

inside it copies its mirror

c_{m} = 2 C - c

, giving the free bound

rad [c] \leftarrow min (rad [c^{'}], R - c)

before extending past

R

Expanding a palindrome at centre

c

on the transformed string

S = |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

rad [c]

is the count of matched steps; if

c + rad [c]

passes the old right edge,

(C, R)

advances to here

Algorithm 6:

\textsc{Manacher}(T)

— radius of the longest palindrome at every centre in

O(n)

1
$S \gets$ interleave $T$ with separators and end sentinels
2
$C \gets 0;\ R \gets 0$
3
for $c \gets 1$ to $|S| - 2$ do
4
if $c < R$ then
5
$\mathit{rad}[c] \gets \min(R - c,\ \mathit{rad}[2C - c])$
mirror bound
6
while $S[c + \mathit{rad}[c] + 1] = S[c - \mathit{rad}[c] - 1]$ do
7
$\mathit{rad}[c] \gets \mathit{rad}[c] + 1$
extend past $R$
8
if $c + \mathit{rad}[c] > R$ then
9
$C \gets c;\ R \gets c + \mathit{rad}[c]$
advance the box
10
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} rad [c]$ ), and $\sum_{c} ⌈ rad [c] /1 ⌉$ over real centres counts all palindromic substrings, both in $O (n)$ .

manacher.pypython

def manacher_radii(text: str) -> list[int]:
  """
    The palindromic radius at every centre of the separator-interleaved form\n
    of `text`. For transformed string S = `^|a|b|a|$`, entry c is the radius\n
    of the longest palindrome of S centred at c. Runs in O(n).\n
    The empty text yields the radii of just the boundary sentinels.\n
  """
  # interleave with '|' and bracket with distinct end sentinels '^' and '$'
  # so no real comparison ever runs off the ends.
  transformed: str = "^|" + "|".join(text) + "|$"
  length: int = len(transformed)
  radius: list[int] = [0 for _ in range(length)]

  center: int = 0
  right_edge: int = 0
  for position in range(1, length - 1):
    if position < right_edge:

      # the mirror centre across `center` gives a free lower bound.
      mirror: int = 2 * center - position
      radius[position] = min(right_edge - position, radius[mirror])

    # extend past the known edge by direct character comparison.
    while (
      transformed[position + radius[position] + 1]
      == transformed[position - radius[position] - 1]
    ):
      radius[position] += 1

    # slide the rightmost palindrome if this one reaches further.
    if position + radius[position] > right_edge:
      center = position
      right_edge = position + radius[position]

  return radius

def longest_palindromic_substring(text: str) -> str:
  """
    The longest palindromic substring of `text`. The radius in the\n
    transformed string equals the length of the palindrome in the original,\n
    and its centre maps back to a start index. Ties pick the leftmost.\n
  """
  if text == "":
    return ""

  # the widest radius marks the centre of the longest palindrome.
  radius: list[int] = manacher_radii(text)
  best_length: int = 0
  best_center: int = 0
  for center, value in enumerate(radius):
    if value > best_length:
      best_length = value
      best_center = center

  # map the transformed centre back to a start index in the original text.
  start: int = (best_center - best_length) // 2
  return text[start : start + best_length]

def count_palindromic_substrings(text: str) -> int:
  """
    The number of non-empty palindromic substrings of `text`, counting each\n
    distinct (start, end) occurrence. Each centre contributes\n
    ceil(radius / 2) palindromes in the original string.\n
  """
  radius: list[int] = manacher_radii(text)

  # each transformed centre's radius covers (radius + 1) // 2 real palindromes.
  return sum((value + 1) // 2 for value in radius)

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 $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} LCP [i]$ ) and the count of distinct substrings ( $\sum (n - SA [i]) - \sum 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, § — Suffix Trees and Arrays: suffix arrays as the space-efficient successor to suffix trees, with binary-search substring queries. ↩
Erickson, Ch. — String Matching: the LCP array, Kasai's linear-time construction, and the distinct-substring and longest-repeat corollaries. ↩
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. ↩