The Knuth-Morris-Pratt (KMP) pattern matching algorithm is an efficient string searching method developed by Donald Knuth, James H. Morris, and Vaughan Pratt in the year 1970. It is used to find the occurrences of a "pattern" within a "text" without checking every single character in the text, which is a significant improvement over the brute-force approach.
The KMP algorithm compares the pattern to the text in left-to-right, but shifts the pattern, P more intelligently than the brute-force algorithm. When a mismatch occurs, what is the most we can shift the pattern so as to avoid redundant comparisons. The answer is that the largest prefix of P[0..j] that is a suffix of P[1.j].
Here's a step-by-step explanation of how the KMP algorithm works:
The core idea to preprocess the pattern to construct an LPS(Longest Prefix Suffix) array. This array stores the length of the longest proper prefix which is also a suffix for each sub-pattern of the pattern. This preprocessing helps in determining the next positions in the pattern to be compared, thus avoiding redundant comparisons.
Once the preprocessing is done, the actual search begins:
The algorithm terminates when either
Function KMP(T:text, P:pattern)
n: lenght of T, i: index of T
m: lenght of P, j: index of P
lps[j] is a array, for j=0 to m-1
lps[]=computeLPSArray(P)
i:=0, j:=0
while i < n
if(P(j) = T(i)) then
if(j = m-1)then
return true
increment i and j
else if(j > 0) then
j = lps[j-1]
else
increment i
return false
Function computeLPSArray(P:pattern)
m: lenght of P
len:=0, i:=1
while(i < m)
if(P[len] = P[i]) then
lps[i]=len+1;
increment len and i
else if(j>0) then
len=lps[len-1]
else
lps[i]=0
increment i