In computer science, the Knuth–Morris–Pratt algorithm (or KMP algorithm) is a string-searching algorithm that searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters. The algorithm was conceived by James H. Morris and independently discovered by Donald Knuth "a few weeks later" from automata theory. Morris and Vaughan Pratt published a technical report in 1970. The three also published the algorithm jointly in 1977. Independently, in 1969, Matiyasevich discovered a similar algorithm, coded by a two-dimensional Turing machine, while studying a string-pattern-matching recognition problem over a binary alphabet. This was the first linear-time algorithm for string matching.
Background A string-matching algorithm wants to find the starting index m in string s that matches the search word w. The most straightforward algorithm, known as the "brute-force" or "naive" algorithm, is to look for a word match at each index m, i.e. the position in the string being searched that corresponds to the character s[m]. At each position m the algorithm first checks for equality of the first character in the word being searched, i.e. s[m] =? w[0]. If a match is found, the algorithm tests the other characters in the word being searched by checking successive values of the word position index, i. The algorithm retrieves the character w[i] in the word being searched and checks for equality of the expression S[m+i] =? W[i]. If all successive characters match in W at position m, then a match is found at that position in the search string. If the index m reaches the end of the string then there is no match, in which case the search is said to "fail". Usually, the trial check will quickly reject the trial match. If the strings are uniformly distributed random letters, then the chance that characters match is 1 in 26. In most cases, the trial check will reject the match at the initial letter. The chance that the first two letters will match is 1 in 676 (1 in 26^2 chances of a match over 26 possible letters). So if the characters are random, then the expected complexity of searching string s of length n is on the order of n comparisons or Θ(n). The expected performance is very good. If s is 1 million characters and w is 1000 characters, then the string search should complete after about 1.04 million character comparisons. That expected performance is not guaranteed. If the strings are not random, then checking a trial m may take many character comparisons. The worst case is if the two strings match in all but the last letter. Imagine that the string s consists of 1 million characters that are all A, and that the word w is 999 A characters terminating in a final B character. The simple string-matching algorithm will now examine 1000 characters at each trial position before rejecting the match and advancing the trial position. The simple string search example would now take about 1000 character comparisons times 1 million positions for 1 billion character comparisons. If the length of w is k, then the worst-case performance is O(k⋅n). The KMP algorithm has a better worst-case performance than the straightforward algorithm. KMP spends a little time precomputing a table (on the order of the size of w, O(k)), and then it uses that table to do an efficient search of the string in O(n). The difference is that KMP makes use of previous match information that the straightforward algorithm does not. In the example above, when KMP sees a trial match fail on the 1000th character (i = 999) because s[m + 999] ≠ w[999], it will increment m by 1, but it will know that the first 998 characters at the new position already match. KMP matched 999 A characters before discovering a mismatch at the 1000th character (position 999). Advancing the trial match position m by one throws away the first A, so KMP knows there are 998 A characters that match w and does not retest them; that is, KMP sets i to 998. KMP maintains its knowledge in the precomputed table and two state variables. When KMP discovers a mismatch, the table determines how much KMP will increase (variable m) and where it will resume testing (variable i).
KMP algorithm
Example of the search algorithm To illustrate the algorithm's details, consider a (relatively artificial) run of the algorithm, where W = "ABCDABD" and S = "ABC ABCDAB ABCDABCDABDE". At any given time, the algorithm is in a state determined by two integers:
m, denoting the position within S where the prospective match for W begins, i, denoting the index of the currently considered character in W. In each step the algorithm compares S[m+i] with W[i] and increments i if they are equal. This is depicted, at the start of the run, like
The algorithm compares successive characters of W to "parallel" characters of S, moving from one to the next by incrementing i if they match. However, in the fourth step S[3] = ' ' does not match W[3] = 'D'. Rather than beginning to search again at S[1], we note that no 'A' occurs between positions 1 and 2 in S; hence, having checked all those characters previously (and knowing they matched the corresponding characters in W), there is no chance of finding the beginning of a match. Therefore, the algorithm sets m = 3 and i = 0.
This match fails at the initial character, so the algorithm sets m = 4 and i = 0
Here, i increments through a nearly complete match "ABCDAB" until i = 6 giving a mismatch at W[6] and S[10]. However, just prior to the end of the current partial match, there was that substring "AB" that could be the beginning of a new match, so the algorithm must take this into consideration. As these characters match the two characters prior to the current position, those characters need not be checked again; the algorithm sets m = 8 (the start of the initial prefix) and i = 2 (signaling the first two characters match) and continues matching. Thus the algorithm not only omits previously matched characters of S (the "AB"), but also previously matched characters of W (the prefix "AB").
… excerpt ends here. Continue reading the full article.
