The KMP algorithm is an algorithm in computer science for searching for ocurrences of matches to a specified word, being the pattern within a given list. Upon finding a partial match, the algorithm then can determine, possibly, where the next partial / full match could be, which avoids the searching of already matched characters.
Here is an example of how the algorithm works:
Let's say the pattern (word) is denoted by the variable W.
The given list (string) shall be S.
M is the position within W where the match shall begin.
And I denotes the character being examined for a possible match.
1 2
M: 0123456789012345678901234567
S: ABDFECADBCAEF FABCD CBDFFEAA
W: ADBC
I: ...
1 & 2 denotes the carrying over after 9. This just makes it shorter to reference.
M is the position of every character within S, including spaces.
W is the pattern we are trying to find within S.
I is the incrementation of finding a match. It stops at the end of the match, if one is found or or until S contains no more characters to be examined for matches, in other words: the search fails.
Now, I'll explain how this works:
What we are searching for is W within S. If a match is found on the first character, we increment I by +1, and move onto the next character in S, if it does not match, we set I to 0 and M to how far we have searched within S.
Now, let's run through S to find a match:
M: 0123456789012345678901234567
S: ABDFECADBCAEF FABCD CBDFFEAA
W: ADBC
I: 0123456789
There is no match at M - Position 0, so we increment I+1, and move onto the next.
Still no match.
We repeat incrementing I+1, until a we find the match AND no match proceeds after the character we had just matched.
Since we have found a full match at M - Position 9, we can check to see if there is another possible match, by further incrementing I+1. However, there is no need, since we have already found the match.
I has been incremented 10 times, and found at M - Position 9.
The search has succeeded!
This is how the Knuth-Morris-Pratt (KMP) algorithm works.
I hope you enjoyed this tutorial.
https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
Here is an example of how the algorithm works:
Let's say the pattern (word) is denoted by the variable W.
The given list (string) shall be S.
M is the position within W where the match shall begin.
And I denotes the character being examined for a possible match.
1 2
M: 0123456789012345678901234567
S: ABDFECADBCAEF FABCD CBDFFEAA
W: ADBC
I: ...
1 & 2 denotes the carrying over after 9. This just makes it shorter to reference.
M is the position of every character within S, including spaces.
W is the pattern we are trying to find within S.
I is the incrementation of finding a match. It stops at the end of the match, if one is found or or until S contains no more characters to be examined for matches, in other words: the search fails.
Now, I'll explain how this works:
What we are searching for is W within S. If a match is found on the first character, we increment I by +1, and move onto the next character in S, if it does not match, we set I to 0 and M to how far we have searched within S.
Now, let's run through S to find a match:
M: 0123456789012345678901234567
S: ABDFECADBCAEF FABCD CBDFFEAA
W: ADBC
I: 0123456789
There is no match at M - Position 0, so we increment I+1, and move onto the next.
Still no match.
We repeat incrementing I+1, until a we find the match AND no match proceeds after the character we had just matched.
Since we have found a full match at M - Position 9, we can check to see if there is another possible match, by further incrementing I+1. However, there is no need, since we have already found the match.
I has been incremented 10 times, and found at M - Position 9.
The search has succeeded!
This is how the Knuth-Morris-Pratt (KMP) algorithm works.
I hope you enjoyed this tutorial.
https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
