KMP refers to Knuth-Morris-Pratt exact string matching. This algorithm is an effective solution to the following problem: Given a (short) pattern and a (long) text, both strings, determine whether the pattern appears somewhere in the text.

The KMP idea, at its core, boils down to two improvements on the naive method, where the naive method is to make every possible pattern-text comparison.

The first improvement is that you can skip over parts that you are sure cannot match. Say your pattern is "abc" and your text is "ababc": you can skip over comparing the pattern to the text starting at letter 2 in the text because you know that (a) the first two letters in the pattern are different and (b) these two different letters correctly match up with the text. Thus, the second character in the text and the first character in the pattern cannot match, so we don't even bother with a comparison.

The second improvement is that, if there has already been a false comparison made, it can be skipped. Let's look at this pattern and text pair:

text:    abbababc
pattern: ababc

The third letter in both the text and pattern match up. But by looking at the pattern, we can already see that the first and third letter in the pattern are identical. Thus, with a little bit of analysis of the pattern beforehand, we can skip comparison at the third character in the text and skip ahead to the fourth, saving lots of time over a long text.

In summary, KMP makes text searches much faster than before.

Log in or register to write something here or to contact authors.