47.04.07 · theoretical-cs / algorithms-analysis

String Algorithms: KMP, Suffix Arrays, and Aho-Corasick

shipped3 tiersLean: none

Anchor (Master): Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §31.1-31.4; Gusfield 1997 Algorithms on Strings, Trees, and Sequences (Cambridge) Ch. 1-3 (suffix trees and arrays, LCP arrays, Aho-Corasick as a generalisation of KMP to automata)

Intuition Beginner

You have a long document and want to find every occurrence of the word "abracadabra." The obvious way is to check every starting position: try position 1, then position 2, and so on. Each check compares up to 11 characters. For a document of length $n$ , this takes up to $11 n$ comparisons — slow if the pattern or text is long.

The problem is that this naive approach forgets what it has learned. Suppose you are matching "aab" against the text "aaab." You compare positions 1-3: "aaa" vs "aab" — mismatch at position 3. The naive approach starts over at position 2. But you already know the first two characters of the text are "aa," which is also a prefix of "aab." You should not recheck them.

The Knuth-Morris-Pratt (KMP) algorithm captures this insight. It precomputes a "failure function" that tells you, after a mismatch, how many characters you can skip without rechecking. The text is scanned left to right without ever backing up.

Suffix arrays solve a different problem: what if you want to search for many different patterns in the same long text? Instead of scanning the text each time, you sort all suffixes of the text alphabetically. Then searching for a pattern is just binary search among the sorted suffixes.

Aho-Corasick generalises KMP to multiple patterns simultaneously. You build a trie (prefix tree) of all patterns and add "failure links" that work like KMP's failure function. Scanning the text once finds all occurrences of all patterns.

Visual Beginner

KMP failure function for pattern "aabbaab":

Position q	1	2	3	4	5	6	7
P[q]	a	a	b	b	a	a	b
pi[q]	0	1	0	0	1	2	3

The failure function $π [q]$ gives the length of the longest proper prefix of $P [1.. q]$ that is also a suffix. For $q = 2$ : "aa" has prefix "a" = suffix "a", so $π [2] = 1$ . For $q = 6$ : "aabbaa" has longest prefix-suffix "aa", so $π [6] = 2$ .

A suffix array for text "banana$":

Index	Suffix	Sorted position
7	$	1
4	ana$	3
1	banana$	5
3	nana$	7

Search for "ana": binary search finds it at sorted positions 3-4 (indices 4, 2).

Worked example Beginner

We run KMP on text $T$ = "aabababaac" and pattern $P$ = "aabaa".

Step 1. Compute failure function for "aabaa":

$π [1] = 0$ (single character has no proper prefix-suffix). $π [2] = 1$ ("aa": prefix "a" = suffix "a"). $π [3] = 0$ ("aab": no prefix = suffix). $π [4] = 1$ ("aaba": prefix "a" = suffix "a"). $π [5] = 2$ ("aabaa": prefix "aa" = suffix "aa").

Step 2. Match $T$ against $P$ :

$q = 0, i = 1$ . Compare $T [1] = a = P [1]$ . $q = 1$ . $q = 1, i = 2$ . Compare $T [2] = a = P [2]$ . $q = 2$ . $q = 2, i = 3$ . Compare $T [3] = b = P [3]$ . $q = 3$ . $q = 3, i = 4$ . Compare $T [4] = a \neq = P [4] = a$ . Wait, $P [4] = a$ and $T [4] = a$ . Match! $q = 4$ .

Let me redo with a clearer trace. $P$ = "aabaa", $T$ = "aabababaac".

$i = 1$ : $T [1] = a, P [1] = a$ . Match. $q = 1$ . $i = 2$ : $T [2] = a, P [2] = a$ . Match. $q = 2$ . $i = 3$ : $T [3] = b, P [3] = b$ . Match. $q = 3$ . $i = 4$ : $T [4] = a, P [4] = a$ . Match. $q = 4$ . $i = 5$ : $T [5] = b, P [5] = a$ . Mismatch! Use $π [4] = 1$ . $q = 1$ .

Now $q = 1, i = 5$ : $T [5] = b, P [2] = a$ . Mismatch. Use $π [1] = 0$ . $q = 0$ .

$q = 0, i = 5$ : $T [5] = b \neq = P [1] = a$ . Advance $i = 6$ .

$i = 6$ : $T [6] = a, P [1] = a$ . Match. $q = 1$ . $i = 7$ : $T [7] = b, P [2] = a$ . Mismatch. $π [1] = 0$ . $q = 0$ . $q = 0$ : $T [7] = b \neq = P [1] = a$ . $i = 8$ . $i = 8$ : $T [8] = a, P [1] = a$ . $q = 1$ . $i = 9$ : $T [9] = a, P [2] = a$ . $q = 2$ . $i = 10$ : $T [10] = c, P [3] = b$ . Mismatch. $π [2] = 1$ . $q = 1$ . $q = 1$ : $T [10] = c \neq = P [2] = a$ . $π [1] = 0$ . $q = 0$ . $q = 0$ : $T [10] = c \neq = P [1] = a$ . $i = 11$ . End of text.

No matches found in this trace (the pattern "aabaa" does not occur in "aabababaac").

Check your understanding Beginner

Formal definition Intermediate+

Definition (string-matching problem). Given a pattern $P [1.. m]$ and a text $T [1.. n]$ over an alphabet $Σ$ , find all shifts $s \in {0, 1, \dots, n - m}$ such that $T [s + 1.. s + m] = P [1.. m]$ .

Definition (KMP failure function). The failure function (also called the prefix function) for pattern $P [1.. m]$ is:

π [q] = max {k : 1 \leq k < q and P [1.. k] is a suffix of P [1.. q]}

for $q = 1, \dots, m$ . By convention, $π [q] = 0$ if no such $k$ exists.

Theorem (KMP running time). The KMP algorithm computes the failure function in $O (m)$ time and finds all occurrences of $P$ in $T$ in $O (n)$ time, for a total of $O (n + m)$ .

Proof sketch. The failure function computation uses an amortised argument: the variable $k$ (current prefix length) starts at 0, increases by at most 1 per iteration (to at most $m$ ), and the total number of decreases across all iterations is bounded by the total increases, which is at most $m$ . So the total work is $O (m)$ .

For matching: the text index $i$ advances monotonically from 1 to $n$ . The pattern index $q$ increases by at most 1 per character of text (total increases bounded by $n$ ) and decreases by at least 1 per failure-function step (total decreases bounded by total increases). So the total matching work is $O (n)$ . $□$

Definition (suffix array). The suffix array $SA$ of a string $T [1.. n]$ is a permutation of ${1, \dots, n}$ such that $T [SA [1] .. n] < T [SA [2] .. n] < \dots < T [SA [n] .. n]$ in lexicographic order.

Definition (LCP array). The longest common prefix array $LCP$ is defined by $LCP [i] = ∣ lcp (T [SA [i - 1] .. n], T [SA [i] .. n]) ∣$ for $i = 2, \dots, n$ .

The LCP array accelerates pattern search in the suffix array: when binary searching for a pattern, the LCP with the current midpoint tells you how many characters have already been matched, avoiding redundant comparisons.

Definition (Aho-Corasick automaton). Given a set of patterns ${P_{1}, \dots, P_{k}}$ , the Aho-Corasick automaton is a finite automaton (a trie augmented with failure links) that recognises the language $Σ^{*} (P_{1} \cup \dots \cup P_{k}) Σ^{*}$ .

The goto function $g (q, a)$ follows trie edges.
The failure function $f (q)$ gives the longest proper suffix of the path to $q$ that is also a trie node (analogous to KMP's failure function).
The output function $out (q)$ lists all patterns that end at node $q$ .

Theorem (Aho-Corasick running time). The Aho-Corasick automaton can be built in $O (m_{1} + \dots + m_{k})$ time and searches a text of length $n$ in $O (n + z)$ time where $z$ is the number of matches.

Counterexamples to common slips

"KMP is always faster than the naive algorithm." For short patterns or random text, the naive algorithm is often faster in practice due to lower constant factors. KMP's advantage is worst-case efficiency on adversarial inputs.
"A suffix array is the same as a suffix tree." A suffix array stores the same information as a suffix tree but in a more compact form ( $n$ integers vs $O (n)$ tree nodes). Some operations are slower on suffix arrays but the space savings are significant.
"Aho-Corasick is just running KMP multiple times." Aho-Corasick shares computation across patterns. The trie merges common prefixes, and failure links allow all patterns to be tracked simultaneously in a single pass over the text.

Key theorem with proof Intermediate+

Theorem (suffix array construction in $O (n l g n)$ ). The suffix array of a string of length $n$ can be constructed in $O (n l g n)$ time using a prefix-doubling approach.

Proof sketch. Sort suffixes by their first character. Then sort by their first 2 characters (using the sort-by-1 as a tiebreaker). Then by 4, 8, etc. After $⌈ l g n ⌉$ doubling steps, the sort is by the full suffix. Each step sorts $n$ items by a key from a bounded alphabet (pairs of ranks from the previous step), which can be done in $O (n)$ using radix sort. Total: $O (n l g n)$ .

More precisely, let $rank_{k} (i)$ be the rank of $T [i .. i + k - 1]$ among all length- $k$ substrings. Initially, $rank_{1} (i) = T [i]$ . To compute $rank_{2 k}$ , sort the pairs $(rank_{k} (i), rank_{k} (i + k))$ . Each sorting step takes $O (n)$ with radix sort, and we need $⌈ l g n ⌉$ steps. $□$

Bridge. String algorithms are the foundational reason pattern matching can be done in linear time: KMP avoids redundant comparisons by exploiting the prefix structure of the pattern, suffix arrays enable indexed search by sorting suffixes, and Aho-Corasick generalises KMP to multiple patterns using automata theory. This builds toward the regular expression engines of 47.01.03, where automata-based matching handles patterns described by regular expressions, and it appears again in 47.01.02, where the NFA-to-DFA conversion parallels the trie-to-automaton construction in Aho-Corasick. The central insight is that the prefix structure of strings — what overlaps exist between prefixes and suffixes — is exactly the information needed to avoid redundant work. Putting these together with the automata theory of 47.01.01 yields a complete picture: string matching is pattern recognition, and the right automaton makes it efficient.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Trace KMP on text "abababcabc" and pattern "ababc". Show the failure function and each step of matching.

Answer

Pattern "ababc": $π = [0, 0, 1, 2, 0]$ .

$π [1] = 0$ , $π [2] = 0$ ("ab"), $π [3] = 1$ ("aba": "a"), $π [4] = 2$ ("abab": "ab"), $π [5] = 0$ ("ababc": no prefix-suffix overlap).

Matching: $q = 0, i = 1$ : $T [1] = a = P [1]$ . $q = 1$ . $q = 1, i = 2$ : $T [2] = b = P [2]$ . $q = 2$ . $q = 2, i = 3$ : $T [3] = a = P [3]$ . $q = 3$ . $q = 3, i = 4$ : $T [4] = b = P [4]$ . $q = 4$ . $q = 4, i = 5$ : $T [5] = a \neq = P [5] = c$ . Mismatch. $π [4] = 2$ . $q = 2$ . $q = 2, i = 5$ : $T [5] = a = P [3]$ . $q = 3$ . $q = 3, i = 6$ : $T [6] = b = P [4]$ . $q = 4$ . $q = 4, i = 7$ : $T [7] = c = P [5]$ . $q = 5$ . Match at shift $i - m = 7 - 5 = 2$ !

Wait, the match occurs when $q$ reaches $m$ . After matching at $i = 7$ , $q = 5 = m$ . Shift is $i - m + 1 = 3$ (1-indexed). Pattern "ababc" found at position 3 in the text "abababcabc". Let me verify: $T [3..7] = abab c$ . Yes!

Continue: $π [5] = 0$ , $q = 0$ . $q = 0, i = 7$ : already processed. $i = 8$ . $q = 0, i = 8$ : $T [8] = a = P [1]$ . $q = 1$ . $q = 1, i = 9$ : $T [9] = b = P [2]$ . $q = 2$ . $q = 2, i = 10$ : $T [10] = c \neq = P [3] = a$ . $π [2] = 0$ . $q = 0$ . $q = 0, i = 10$ : $T [10] = c \neq = P [1]$ . $i = 11$ . End.

One match found at position 3.

Exercise 5 (medium, short answer).

Explain how the Aho-Corasick automaton processes the text "ushers" with patterns {"he", "she", "his", "hers"}. List the matches found.

Answer

The trie has paths: h→e, s→h→e, h→i→s, h→e→r→s. Failure links: from node for "he" back to "e" (if present), from "she" back to "he", etc.

Processing "ushers":

$u$ : no match, follow failure to root.
$s$ : follow trie edge s.
$h$ : follow trie edge h (now at "sh").
$e$ : follow trie edge e (now at "she"). Output: "she" at position 2. Follow failure to "he". Output: "he" at position 2.
$r$ : follow trie edge r (now at "her").
$s$ : follow trie edge s (now at "hers"). Output: "hers" at position 2.

Matches: "she" at position 2, "he" at position 2, "hers" at position 2. (All starting at 0-indexed position 2 in "ushers".)

Exercise 6 (hard, symbolic).

Prove that the KMP matching phase makes at most $2 n$ character comparisons on a text of length $n$ .

Hint

Use a potential-function argument: the potential is $q$ (current pattern position). Each comparison either increases $q$ (matching) or decreases $q$ via the failure function.

Answer

Each iteration of the matching loop either: (a) matches and increments $q$ , or (b) mismatches and follows the failure function, decreasing $q$ . In case (b), if $q = 0$ and there is a mismatch, $i$ advances without changing $q$ .

Consider the quantity $k = i + q$ (text position + pattern position). A matching step increases $k$ by 1 (both $i$ and $q$ may change, but $k$ increases). A failure-function step decreases $q$ by at least 1 while keeping $i$ fixed, so $k$ decreases by at least 1. When $q = 0$ and there is a mismatch, $i$ advances and $k$ increases by 1.

The total number of matching steps is at most $n$ (bounded by text length). The total number of failure-function steps is bounded by the total matching steps (since $q$ cannot go below 0). So the total number of iterations is at most $2 n$ . Each iteration makes at most 1 comparison, so total comparisons $\leq 2 n$ . Rubric: full credit for the potential argument.

Exercise 9 (medium, symbolic).

Given a suffix array for "banana$" with SA = [7, 6, 4, 2, 1, 5, 3] and LCP = [-, 0, 1, 3, 0, 0, 2], search for the pattern "nan" using binary search on the suffix array.

Answer

Suffixes in sorted order: " $", " a$ ", "ana $", " anana$ ", "banana $", " na$ ", "nana$".

Binary search for "nan":

Low = 1, High = 7. Mid = 4. Suffix SA[4] = "anana $". C o m p a r e " nan " v s " ana " : n > a, sose a r c h r i g h t ha l f . - L o w = 5, H i g h = 7. M i d = 6. S u f f i x S A [6] = " na$ ". Compare "nan" vs "na $" : n = n, a = a, n >$ (end). So "nan" > "na $", se a r c h r i g h t . - L o w = 7, H i g h = 7. M i d = 7. S A [7] = " nana$ ". Compare "nan" vs "nan": match first 3 chars. Found! Pattern "nan" occurs at position SA[7] - 1 + ... wait. SA[7] = 3. Suffix starting at position 3 is "nana $"." nan " i s a p r e f i x o f " nana$ ", so "nan" occurs at position 3 in "banana$". Check: "banana"[3..5] = "nan". Correct!

Lean formalization Intermediate+

Mathlib has String, List, and Array with basic lemmas but no formalisation of KMP, suffix arrays, or Aho-Corasick. The foundational gap is the absence of the KMP failure function and its correctness proof (showing the algorithm finds all and only valid shifts), the suffix array data structure with its construction and search operations, and the Aho-Corasick automaton with failure links. A formalisation of KMP would require proving that the failure function correctly computes the longest proper prefix-suffix and that the matching phase is complete (finds all occurrences). This unit ships without a lean_module.

Advanced results Master

Three results extend the basic string algorithm toolkit.

Theorem 1 (linear-time suffix array construction). The suffix array of a string of length $n$ can be constructed in $O (n)$ time using the SA-IS (Suffix Array Induced Sorting) algorithm of Nong, Zhang, and Chan (2011).

SA-IS is based on the observation that suffixes can be classified into L-type and S-type, and that the S-type suffixes form a recursively smaller subproblem. The algorithm recursively sorts the S-type suffixes and then uses induced sorting to place the L-type suffixes. This achieves $O (n)$ worst-case time, matching the theoretical bound for suffix tree construction.

Theorem 2 (LCP array from suffix array in linear time). Given the suffix array and the text, the LCP array can be computed in $O (n)$ time using Kasai's algorithm.

Kasai's algorithm processes suffixes in text order (not SA order). The key insight is that the LCP of consecutive suffixes in text order differs by at most 1 from the LCP of the previous pair, allowing the computation to proceed in amortised $O (1)$ per position ^{[Gusfield Ch. 3]}.

Theorem 3 (Aho-Corasick as automaton). The Aho-Corasick automaton is a DFA (in the sense of 47.01.01) whose language is $Σ^{*} (P_{1} \cup \dots \cup P_{k}) Σ^{*}$ . The number of states is $O (\sum m_{i})$ and the construction time is $O (\sum m_{i} \cdot ∣Σ∣)$ .

The Aho-Corasick automaton generalises the KMP automaton (which is the special case $k = 1$ ). The failure links play the same role as the KMP failure function: they allow the automaton to "fall back" to the longest matching prefix without reprocessing any text characters. This connects string matching directly to automata theory.

Synthesis. String algorithms are the foundational reason pattern matching can be done efficiently: KMP exploits prefix structure for linear-time matching, suffix arrays enable indexed search by sorting, and Aho-Corasick extends the approach to multiple patterns using automata. The central insight is that the prefix-suffix structure of strings — captured by the failure function, the suffix array ordering, or the trie with failure links — is exactly the information needed to avoid redundant comparisons. This builds toward the regular expression engines of 47.01.03 and the NFA constructions of 47.01.02, where the same automata-theoretic ideas handle more complex patterns. Putting these together yields a layered approach to string processing: exact matching (KMP), indexed search (suffix arrays), and multi-pattern matching (Aho-Corasick), each building on the same structural insights about how strings overlap.

Full proof set Master

Proposition 1 (KMP failure function correctness). For each $q \in {1, \dots, m}$ , $π [q]$ equals the length of the longest proper prefix of $P [1.. q]$ that is also a suffix of $P [1.. q]$ .

Proof. The failure function computation iterates $q$ from 2 to $m$ . At each step, it maintains the invariant that $k$ is the length of the longest proper prefix of $P [1.. q - 1]$ that is also a suffix. If $P [k + 1] = P [q]$ , then $k + 1$ is a prefix-suffix of $P [1.. q]$ . Otherwise, it follows the chain of decreasing $k$ values (via $π [k]$ ) until either a match is found or $k = 0$ . By induction on $q$ , the invariant holds and $π [q]$ is computed correctly. $□$

Proposition 2 (KMP matching finds all occurrences). If $P$ occurs in $T$ at shift $s$ , then KMP reports shift $s$ .

Proof. When KMP processes text position $i = s + m$ , the pattern pointer $q$ equals $m$ (all characters matched). At this point, the algorithm reports the match at shift $i - m = s$ . The failure function ensures that $q$ never skips a valid partial match: if $P [1.. q]$ matches $T [i - q + 1.. i]$ and the next character mismatches, then $q$ is set to $π [q]$ , which is the longest proper prefix of $P [1.. q]$ that could start a new match. This is exactly the right amount of backtracking — no valid shift is missed. $□$

Proposition 3 (suffix array search correctness). Binary search on the suffix array finds all occurrences of $P [1.. m]$ in $T [1.. n]$ .

Proof. The suffixes in SA order are lexicographically sorted. The pattern $P$ defines a lexicographic range: all suffixes starting with $P$ are contiguous in the sorted order. Binary search finds the leftmost and rightmost suffixes in this range. Each such suffix $SA [i]$ corresponds to an occurrence of $P$ at position $SA [i]$ in $T$ . Since all suffixes starting with $P$ are found, all occurrences are found. $□$

Connections Master

47.01.01 — DFAs are the foundation for the KMP and Aho-Corasick automata; each string-matching algorithm builds a specific DFA that recognises the pattern language.
47.01.02 — The Aho-Corasick automaton uses failure links analogous to the NFA subset construction: both convert nondeterministic state tracking into deterministic transitions.
47.01.03 — Regular expressions generalise exact string matching; the Thompson construction builds NFAs from regex that are processed by techniques similar to KMP and Aho-Corasick.
47.04.01 — Amortized analysis justifies the $O (n + m)$ bound of KMP: the potential (pattern position) bounds total work across the entire matching phase.

Historical & philosophical context Master

The Knuth-Morris-Pratt algorithm was discovered independently by Knuth and Pratt (1970) and by Morris (1970), and published jointly in 1977. Knuth credits the key insight to Morris, who was implementing a text editor and needed an efficient search algorithm. The failure function was independently discovered by several researchers, highlighting that the prefix-suffix structure is a natural and unavoidable concept in string matching ^{[CLRS §31.3 notes]}.

The Aho-Corasick algorithm was published by Alfred Aho and Margaret Corasick in 1975, originally developed for bibliographic search in the Bell Labs library system. The algorithm's elegance lies in converting the multi-pattern problem into an automaton construction, bridging string matching and automata theory. The failure links are the exact multi-pattern generalisation of the KMP failure function ^{[Gusfield Ch. 2]}.

Suffix arrays were introduced by Manber and Myers in 1993 as a space-efficient alternative to suffix trees. While suffix trees use $O (n)$ space with a constant factor of about 20 bytes per character, suffix arrays use only 4 bytes per character (one integer). The trade-off is slightly slower query times ( $O (m lo g n)$ vs $O (m)$ for suffix trees), but the space savings made suffix arrays practical for indexing large text corpora like genome sequences. The linear-time SA-IS construction algorithm (2011) closed the theoretical gap between suffix arrays and suffix trees ^{[Gusfield Ch. 3]}.

Bibliography Master

@book{clrs2022,
  author    = {Cormen, Thomas H. and Leiserson, Ronald L. and Rivest, Clifford and Stein, Christopher},
  title     = {Introduction to Algorithms},
  edition   = {4th},
  publisher = {MIT Press},
  year      = {2022},
}
@book{gusfield1997,
  author    = {Gusfield, Dan},
  title     = {Algorithms on Strings, Trees, and Sequences},
  publisher = {Cambridge University Press},
  year      = {1997},
}
@article{aho1975efficient,
  author  = {Aho, Alfred V. and Corasick, Margaret J.},
  title   = {Efficient String Matching: An Aid to Bibliographic Search},
  journal = {Communications of the ACM},
  volume  = {18},
  number  = {6},
  pages   = {333--340},
  year    = {1975},
}
@article{knuth1977fast,
  author  = {Knuth, Donald E. and Morris, James H. and Pratt, Vaughan R.},
  title   = {Fast Pattern Matching in Strings},
  journal = {SIAM Journal on Computing},
  volume  = {6},
  number  = {2},
  pages   = {323--350},
  year    = {1977},
}

Prerequisites

47.04.01
47.01.01

Tier anchors

beginner: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §31.1-31.4 (string matching as finding all occurrences of a pattern in a text, the naive approach and why it is slow, KMP's key idea of avoiding re-checking characters)
intermediate: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §31.1-31.4, §32.2 (KMP failure function, O(n+m) matching, suffix arrays for indexed string search, Aho-Corasick for multiple pattern matching)
master: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §31.1-31.4; Gusfield 1997 Algorithms on Strings, Trees, and Sequences (Cambridge) Ch. 1-3 (suffix trees and arrays, LCP arrays, Aho-Corasick as a generalisation of KMP to automata)

References

Cormen, T. H., Leiserson, R. L., Rivest, C. L. & Stein, C. — Introduction to Algorithms (4th ed.) · MIT Press (2022). Section 31.1 defines the string-matching problem: given a pattern $P [1.. m]$ and text $T [1.. n]$ , find all shifts $s$ such that $P$ occurs in $T$ starting at position $s$ ; the naive algorithm checks each shift in $O (m)$ time for a total of $O ((n - m + 1) m)$ ; Section 31.2 presents the Rabin-Karp fingerprinting method using rolling hashes for $O (n + m)$ expected time; Section 31.3 presents the Knuth-Morris-Pratt algorithm with its failure function $π [q] = max {k : k < q, P [1.. k] is a suffix of P [1.. q]}$ precomputed in $O (m)$ time, enabling matching in $O (n)$ time; Section 31.4 covers the Boyer-Moore algorithm with bad-character and good-suffix heuristics.
Gusfield, D. — Algorithms on Strings, Trees, and Sequences · Cambridge University Press (1997). Chapter 1 introduces the exact string-matching problem and its variants; Chapter 2 develops suffix trees (Weiner 1973, McCreight 1976, Ukkonen 1995) as $O (n)$ constructible indexes supporting $O (m)$ pattern search; Chapter 3 develops suffix arrays (Manber and Myers 1993) as space-efficient alternatives to suffix trees, constructible in $O (n l g n)$ time and supporting $O (m l g n)$ search with binary search; the Aho-Corasick algorithm extends KMP to multiple patterns using a trie with failure links, running in $O (n + m_{1} + \dots + m_{k} + z)$ time where $z$ is the number of matches.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m