KMP String Pattern Matching Algorithm
String matching is one of the most common problems in computer science. It involves finding a specific pattern inside a larger string of text. For example, searching for the word "AWS" inside a large document is a string matching problem.
A simple approach is to compare the pattern with every possible position in the text. However, this can become inefficient when the text is very large. The Knuth–Morris–Pratt (KMP) algorithm provides an efficient solution by avoiding unnecessary comparisons.
What is KMP?
KMP stands for Knuth–Morris–Pratt, named after its creators Donald Knuth, Vaughan Pratt, and James Morris.
The KMP algorithm searches for a pattern in a text in O(n + m) time, where:
nis the length of the text.mis the length of the pattern.
The main idea is to use information from the pattern itself to avoid repeating comparisons.
Why is KMP Efficient?
Suppose we are searching for:
1
Pattern: ABABC
inside:
1
Text: ABABABDABABC
During the search, several characters may match before a mismatch occurs.
A naive algorithm would move the pattern forward and start comparing again from the beginning. KMP realizes that some of the characters have already been matched and can be reused.
To achieve this, KMP creates an array called LPS.
LPS Array
LPS stands for:
Longest Proper Prefix which is also a Suffix
A prefix is a substring that starts from the beginning of string.
A suffix is a substring that ends at the end of string.
For example:
1
String: ABAB
The prefixes are:
1
2
3
A
AB
ABA
The suffixes are:
1
2
3
B
AB
BAB
The longest prefix that is also a suffix is:
1
AB
Therefore:
1
LPS = 2
Example of LPS
Consider the pattern:
1
A B A B C A B A B
The LPS array is:
1
0 0 1 2 0 1 2 3 4
So:
1
2
Pattern: A B A B C A B A B
LPS: 0 0 1 2 0 1 2 3 4
For the last character, the longest proper prefix that is also a suffix is:
1
ABAB
Therefore, the LPS value is
4.How KMP Uses LPS
The most important part of KMP happens when a mismatch occurs.
Suppose:
1
text[i] != pattern[j]
If
j is greater than zero, instead of setting j to zero, KMP does:1
j = LPS[j - 1]
This allows the algorithm to continue from a position where a match is still possible.
The text pointer does not need to move backward.
This is the main reason KMP is faster than the naive approach.
KMP Searching Process
The algorithm maintains two pointers:
1
2
i → text
j → pattern
When the characters match:
1
text[i] == pattern[j]
we move both pointers:
1
2
i++
j++
When there is a mismatch:
1
text[i] != pattern[j]
and
j > 0, we use:1
j = LPS[j - 1]
If
j == 0, we simply move the text pointer:1
i++
When:
1
j == pattern.length
the complete pattern has been found.
Simple Pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Build the LPS array for the pattern
i = 0
j = 0
while i < text.length:
if text[i] == pattern[j]:
i++
j++
if j == pattern.length:
pattern found
j = LPS[j - 1]
else if i < text.length and text[i] != pattern[j]:
if j != 0:
j = LPS[j - 1]
else:
i++
Time Complexity
KMP has excellent performance because both the LPS construction and searching are linear.
| Operation | Complexity |
|---|---|
| LPS construction | O(m) |
| Pattern searching | O(n) |
| Total | O(n + m) |
| Extra space | O(m) |
The naive pattern-matching algorithm can take O(n × m) in the worst case.
Where Can KMP Be Used?
KMP is useful whenever efficient pattern searching is required.
Some examples include:
- Searching text in documents
- Finding keywords in large files
- Log analysis
- DNA sequence matching
- Text editors
- Search applications
- Pattern detection
- Competitive programming
- Technical coding interviews
Key Takeaways
The most important concepts to remember are:
- KMP is a string pattern-matching algorithm.
- It was developed by Knuth, Morris, and Pratt.
- It uses an LPS array.
- LPS means Longest Proper Prefix which is also a Suffix.
- When a mismatch occurs, KMP does not restart the pattern from zero unnecessarily.
- The overall time complexity is O(n + m).
- The key to understanding KMP is understanding how the LPS array is constructed.
Conclusion
The KMP algorithm demonstrates an important principle in algorithm design: preprocessing can make searching much more efficient.
Instead of repeatedly comparing the same characters, KMP learns the structure of the pattern beforehand using the LPS array. This allows it to skip unnecessary comparisons and achieve linear-time pattern matching.
Once the concept of the LPS array is understood, the KMP algorithm becomes much easier to implement and apply to real-world string-searching problems.
KMP is not just an algorithm for interviews—it is a great example of how understanding the structure of data can lead to better and more efficient solutions.
#KMP #StringMatching #Algorithms #DataStructures #Programming #ComputerScience #Coding
Enjoyed reading this content? Let the author know!
Your likes, comments, shares, and saves help creators reach more builders.
Loading recommendations
Loading article