Scribd
Upload
13 views2 pages

KMP Algorithm: Efficient String Matching

The Knuth-Morris-Pratt (KMP) algorithm is an efficient linear-time method for string matching that uses a precomputed Longest Prefix Suffix (LPS) array to avoid redundant comparisons. By intelligently shifting the pattern upon mismatches, KMP ensures that each character in the text is scanned at most once, achieving a time complexity of O(n + m). The document outlines the algorithm's steps for both searching a pattern in a text and computing the LPS array.

Uploaded by

amit.ray455
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
13 views2 pages

KMP Algorithm: Efficient String Matching

The Knuth-Morris-Pratt (KMP) algorithm is an efficient linear-time method for string matching that uses a precomputed Longest Prefix Suffix (LPS) array to avoid redundant comparisons. By intelligently shifting the pattern upon mismatches, KMP ensures that each character in the text is scanned at most once, achieving a time complexity of O(n + m). The document outlines the algorithm's steps for both searching a pattern in a text and computing the LPS array.

Uploaded by

amit.ray455
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

The Knuth-Morris-Pratt (KMP) algorithm is a linear-time string matching algorithm used to

efficiently search for occurrences of a pattern within a text. Unlike naive string matching
which may repeatedly re-examine characters after mismatches, KMP preprocesses the
pattern with an auxiliary "Longest Prefix Suffix" (LPS) array. This LPS array stores lengths
of the longest proper prefixes of the pattern that are also suffixes, allowing the algorithm
to intelligently shift the pattern to avoid redundant comparisons.

KMP compares characters in the pattern with the text sequentially. When a mismatch
occurs, instead of restarting from the next character in the text, it uses the LPS array to
reposition the pattern in a way that skips already matched characters, ensuring every
character of the text is scanned at most once. This optimizes the search with a time
complexity of O(n+ m), where n is the text length and m is the pattern length.

KMP-Algorithm(T, P)
Input: Text T of length n, Pattern P of length m
Output: All occurrences of P in T

1. LPS ← ComputeLPSArray(P)
2. i ← 0 // index for text T
3. j ← 0 // index for pattern P

4. while i < n do
5. if P[j] == T[i] then
6. i←i+1
7. j←j+1
8. if j == m then
9. print "Pattern found at index" i - j
10. j ← LPS[j-1]
11. else if i < n and P[j] != T[i] then
12. if j != 0 then
13. j ← LPS[j-1]
14. else
15. i←i+1

ComputeLPSArray(P)
Input: Pattern P of length m
Output: LPS array

1. length ← 0 // length of previous longest prefix suffix


2. LPS[0] ← 0
3. i ← 1

4. while i < m do
5. if P[i] == P[length] then
6. length ← length + 1
7. LPS[i] ← length
8. i←i+1
9. else
10. if length != 0 then
11. length ← LPS[length-1]
12. else
13. LPS[i] ← 0
14. i←i+1

You might also like