Computer Science
Grade 11
20 min
String Matching Algorithms: Knuth-Morris-Pratt (KMP)
Learn the Knuth-Morris-Pratt (KMP) algorithm for efficient string matching, understanding its pattern matching table and how it avoids unnecessary comparisons.
Tutorial Preview
1
Introduction & Learning Objectives
Learning Objectives
Explain the inefficiency of the naive string matching algorithm by analyzing its worst-case scenario.
Define and compute the Longest Proper Prefix that is also a Suffix (LPS) array for any given pattern.
Trace the KMP algorithm step-by-step on a given text and pattern, showing the state of the text and pattern pointers.
Analyze the time complexity of the KMP algorithm (O(n+m)) and compare it to the naive approach (O(n*m)).
Implement the core logic for both LPS array construction and the KMP search in pseudocode or a high-level programming language.
Identify real-world scenarios where the KMP algorithm provides a significant performance improvement over simpler methods.
Ever used Ctrl+F to find a word in a huge document and wondered how it works so fast? 🕵...
2
Key Concepts & Vocabulary
TermDefinitionExample
Naive String MatchingThe straightforward, brute-force approach where the pattern is compared character-by-character at every possible starting position in the text. If a mismatch occurs, the pattern is shifted by one position to the right.To find 'ABA' in 'ABACABA', the naive method checks at index 0 (match), then shifts to index 1 ('BAC' vs 'ABA'), then index 2 ('ACA' vs 'ABA'), and so on.
Proper PrefixA prefix of a string that is not equal to the string itself.For the string 'PATTERN', the proper prefixes are 'P', 'PA', 'PAT', 'PATT', 'PATTE', and 'PATTER'.
Proper SuffixA suffix of a string that is not equal to the string itself.For the...
3
Core Syntax & Patterns
LPS Array Construction Logic
Initialize lps[0] = 0. Use two pointers, `length` (for the previous longest prefix) and `i` (to iterate through the pattern). If pattern[i] == pattern[length], increment both and set lps[i] = length. If they don't match, update `length` to `lps[length-1]` to find a shorter prefix to check.
This rule is used once to pre-process the pattern string. It builds the LPS array in O(m) time, where m is the length of the pattern. This pre-computation is what enables the main search to be so efficient.
KMP Matching Logic
Use two pointers, `i` for the text and `j` for the pattern. If text[i] == pattern[j], increment both. If a mismatch occurs (text[i] != pattern[j]), do not move `i`. Instead, update `j` to `lps[j-1]`. If `j` was already 0, then increment...
4 more steps in this tutorial
Sign up free to access the complete tutorial with worked examples and practice.
Sign Up Free to ContinueSample Practice Questions
Challenging
Consider a pattern of length `m` consisting of `m` identical characters, such as P = 'AAAAA'. What will its LPS array look like?
A.[0, 0, 0, 0, 0]
B.[0, 1, 2, 3, 4]
C.[0, 1, 0, 1, 0]
D.[0, 1, 1, 1, 1]
Challenging
You are given an incomplete LPS array `[0, 0, 1, 2, 0, 1, ?]` for the 7-character pattern P = 'abacaba'. What is the missing value for `lps[6]` and why?
A.0, because the last character 'a' does not match the character at index `length`=1, which is 'b'.
B.2, because the prefix 'ab' is the longest prefix that appears elsewhere in the pattern.
C.3, because the longest proper prefix of 'abacaba' that is also a suffix is 'aba', which has length 3.
D.7, because the entire pattern is a palindrome.
Challenging
How would you modify the KMP search logic to find and count ALL non-overlapping occurrences of a pattern, instead of stopping after the first one?
A.After finding a match (when `j == m`), increment a counter and reset `j = 0` and `i = i + 1`.
B.After finding a match (when `j == m`), increment a counter and then update `j` using the LPS array (`j = lps[j-1]`) to continue the search from the current position.
C.Run the entire KMP search algorithm in a loop, starting one character later in the text each time.
D.It's not possible; KMP is only designed to find the first occurrence.
Want to practice and check your answers?
Sign up to access all questions with instant feedback, explanations, and progress tracking.
Start Practicing Free