Chapter 5: Knuth-Morris-Pratt Algorithm
This introduction explains why naive string search wastes work on repetitive text and how KMP uses pattern information to avoid backtracking.
After this chapter you will be able to
- LPS Guided Forward Shifts. Explain how KMP uses previously matched characters and the LPS array after a mismatch to shift the pattern without moving the text pointer backward.
- LPS-Guided Mismatch Handling. Explain that KMP uses the LPS array to decide where to resume in the pattern after a mismatch, rather than restarting the pattern or backtracking in the text.
- Longest Matching Prefix and Suffix. Describe how a string can have the same sequence as both a proper prefix and a proper suffix, and identify the longest such sequence in the section’s examples.
- LPS array construction. Describe how to build the LPS array by tracking the length of a matching prefix and suffix as the pattern is scanned. Explain how a mismatch can cause that length to fall back to an earlier LPS value.
- Mismatch pointer updates. Trace how KMP updates its text and pattern pointers after matches and mismatches. Explain how the LPS value lets the search retain an already matched part of the pattern without moving backward in the text.
- Linear time explanation. Explain why the section gives KMP a total time complexity of O(n + m), identifying the preprocessing and search portions.
- Forward Scanning for Data Streams. Explain why the section presents KMP as suitable for continuous, ephemeral data streams, and contrast that use with algorithms that skip comparisons in static environments.
- Forward-only streaming log matching. Explain why searching a live log stream for a specific error type favors KMP: past data may already be discarded, while KMP advances through the stream without moving its text pointer backward and uses the error pattern’s LPS array to manage comparisons and shifts.
- Streaming threat signature matching. Explain how an IDS can preprocess threat signatures into LPS arrays, then inspect incoming bytes sequentially and use the LPS array after a partial match fails to avoid re-evaluating traffic.
- LPS preprocessing trade-offs. Explain that KMP must build the LPS array before scanning the text, taking O(m) time and O(m) auxiliary space for a pattern of length m. Describe why a long, changing pattern can delay a search and why the array can be costly in a memory-constrained device.
- Separate pattern and scan complexity. Explain how analyzing the pattern’s internal symmetries separately lets KMP scan the text in O(n) time with a forward-moving text pointer, and why that suits continuous data streams.
- No-redundancy performance trap. Explain how an all-zero LPS array affects KMP after a mismatch and why repetition in the data matters when choosing KMP over a simpler search.
What it builds on
- Time and Space Complexity (chapter 1) · Uses worst-case time complexity and Big-O notation.
- String matching algorithm (chapter 4) · The earlier string-matching discussion provides context for the contrast with Rabin–Karp.
Section by section
Introduction
This introduction explains why naive string search wastes work on repetitive text and how KMP uses pattern information to avoid backtracking.
- Naive Search Backtracking Cost: Explain how a naive search responds to a mismatch and why repeated characters can make its worst-case running time O(nm).
Why it matters: This wasted work is the problem KMP is designed to avoid. - LPS Guided Forward Shifts: Explain how KMP uses previously matched characters and the LPS array after a mismatch to shift the pattern without moving the text pointer backward.
Why it matters: The LPS table lets KMP use a mismatch to make progress rather than repeat discarded work.
Key terms: backtracking, naive approach, O(nm), KMP, LPS array, proper prefix, proper suffix, preprocessing
5.1 Fast pattern matching
Introduces KMP’s use of an LPS array to skip redundant comparisons and illustrates the repeated prefix-and-suffix pattern that the array captures.
- LPS-Guided Mismatch Handling: Explain that KMP uses the LPS array to decide where to resume in the pattern after a mismatch, rather than restarting the pattern or backtracking in the text.
Why it matters: This is the central reason KMP avoids repeating work during a search. - Longest Matching Prefix and Suffix: Describe how a string can have the same sequence as both a proper prefix and a proper suffix, and identify the longest such sequence in the section’s examples.
Why it matters: Recognizing the repeated block makes the information behind LPS concrete.
Key terms: KMP, LPS array, text pointer, redundant comparisons, proper prefix, proper suffix, Longest Prefix which is also Suffix, redundancy
5.1.1 Building the LPS array
This section builds the LPS array and shows how KMP uses it to skip redundant pattern comparisons while searching in linear time.
- LPS array construction: Describe how to build the LPS array by tracking the length of a matching prefix and suffix as the pattern is scanned. Explain how a mismatch can cause that length to fall back to an earlier LPS value.
Why it matters: The search can skip comparisons only because the array has already captured repetition within the pattern. - Mismatch pointer updates: Trace how KMP updates its text and pattern pointers after matches and mismatches. Explain how the LPS value lets the search retain an already matched part of the pattern without moving backward in the text.
Why it matters: Keeping the text position while adjusting the pattern position avoids repeating comparisons that the pattern's structure has already resolved. - Linear time explanation: Explain why the section gives KMP a total time complexity of O(n + m), identifying the preprocessing and search portions.
Why it matters: It connects the array's preprocessing cost and the pointer behavior to KMP's stated running time.
Key terms: LPS array, prefix-suffix match, length, LPS[0], text pointer i, pattern pointer j, LPS[j - 1], mismatch, O(m), O(n + m)
5.2 Real-World applications
Explains why KMP’s forward-only scan is useful for continuous data streams, even though other string-matching algorithms may be faster on static data.
- Forward Scanning for Data Streams: Explain why the section presents KMP as suitable for continuous, ephemeral data streams, and contrast that use with algorithms that skip comparisons in static environments.
Why it matters: This explains why the fastest algorithm for a static file is not necessarily the best fit for a live stream.
Key terms: KMP, forward-moving linear traversal, continuous ephemeral data streams
5.2.1 Log analysis and real-time data streaming
This section explains why KMP suits real-time log matching when past stream data is discarded.
- Forward-only streaming log matching: Explain why searching a live log stream for a specific error type favors KMP: past data may already be discarded, while KMP advances through the stream without moving its text pointer backward and uses the error pattern’s LPS array to manage comparisons and shifts.
Why it matters: It explains how to look for errors in incoming logs without storing the stream just to revisit earlier characters.
Key terms: live data stream, text pointer, LPS array, pattern shift
5.2.2 Intrusion Detection Systems (IDS)
This section shows how KMP-style pattern matching can help an intrusion detection system scan streaming network traffic for threat signatures without rechecking bytes.
- Streaming threat signature matching: Explain how an IDS can preprocess threat signatures into LPS arrays, then inspect incoming bytes sequentially and use the LPS array after a partial match fails to avoid re-evaluating traffic.
Why it matters: It connects KMP’s handling of mismatches to the need to keep scanning live network traffic.
Key terms: Intrusion Detection Systems (IDS), threat signatures, LPS array, KMP algorithm, pattern pointer
5.3 Key insights
5.3.1 The cost of preprocessing and memory overhead
This section explains the time and memory costs of building KMP’s LPS array before a search can begin.
- LPS preprocessing trade-offs: Explain that KMP must build the LPS array before scanning the text, taking O(m) time and O(m) auxiliary space for a pattern of length m. Describe why a long, changing pattern can delay a search and why the array can be costly in a memory-constrained device.
Why it matters: A faster search may still be a poor fit when preparation delays each search or memory is scarce.
Key terms: LPS array, preprocessing, O(m), auxiliary space, latency bottleneck
5.3.2 Separating complexity
The section explains how separating pattern analysis from text scanning lets KMP scan the text in O(n) time without moving the text pointer backward.
- Separate pattern and scan complexity: Explain how analyzing the pattern’s internal symmetries separately lets KMP scan the text in O(n) time with a forward-moving text pointer, and why that suits continuous data streams.
Why it matters: Separating the two phases explains why KMP can scan a continuous stream without revisiting earlier text.
Key terms: pattern, internal symmetries, scanning phase, O(n), text pointer, historical backtracking
5.3.3 The “No Redundancy" trap
This section explains why KMP may be a poor choice when the pattern and text lack repetition, despite its usefulness for repetitive data such as logs.
- No-redundancy performance trap: Explain how an all-zero LPS array affects KMP after a mismatch and why repetition in the data matters when choosing KMP over a simpler search.
Why it matters: Checking the data for repetition helps you avoid preprocessing that provides no practical benefit.
Key terms: KMP, LPS array, repetition, naive brute-force approach
5.4 Summary
5.5 References
Where this is used later
- (chapter intro) (chapter 6) · Provides the earlier KMP string-matching approach used for contrast.
- The paradigm shift: Right to left scanning (chapter 6) · Provides an earlier pattern-matching approach that also shifts the pattern.
Concepts explained in this chapter
- Knuth-Morris-Pratt algorithmThe Knuth-Morris-Pratt algorithm is a string-search procedure that uses pattern prefix-suffix information to avoid rechecking text characters after a mismatch.
- LPS arrayAn LPS array stores, for each pattern position, the length of the longest proper prefix that is also a suffix of the pattern prefix ending there.
- proper prefixA proper prefix is a sequence at the beginning of a string that is strictly shorter than the entire string.
- prefix-suffix matchA prefix-suffix match is an equality between a proper prefix and a suffix of a character sequence, represented by their shared length.
- O(n + m)A time bound proportional to the combined lengths n and m of two inputs.
- backtrackingSearch backtracking returns to an earlier search state after exploring one branch so that other branches can be examined.
- proper suffixA proper suffix is a sequence at the end of a string that is strictly shorter than the entire string.
- preprocessingPreprocessing is preparatory computation performed on input data before the main algorithmic operation begins.
- pattern shiftA pattern shift is the relocation of a search pattern to a later text position after a comparison result determines that earlier positions can be skipped.
- linear time complexityAn asymptotic linear-time bound in an input of size N, also written O(m) when that input's size is denoted m.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
