Knuth–Morris–Pratt algorithm (KMP)

KMP algorithm is an efficient patterns matching algorithm, used for searching occurences of a pattern string in a text string.

Here, we will use text string 'acabaabaabcaccaabc' and pattern string 'abaabcac' to go throught this algorithm. Press Generate string when you ready!

To locate the occurence of patten string within the text one, the most intuitive method is brute force. That is to compare pattern string with each sub-string of text with same length. Press Brute Force to go on!

Green cube means matching; red cube means unmatching; grey cube shows the sub-string of text which is fully matched with pattern string.

It is inefficient, the worst case of time complexity would be O(n*m), n and m are the length of text and pattern. Click Improvement to see how can we improve the efficiency.

For example, once we had compare sub-string3(start at index=2) with pattern string, we got the first 5 letters 'abaab' matched, and unmatched cubes started at index=7.

We can take advantage of the known partially matched fragment 'abaab', because in following four (4=5-1) substrings (start at index=3,4,5,6) comparisons, all the sub-strings in front of unmatched index=7 are prefixes or suffixes of 'abaab'.

Please click the button 'Pre/Suffix' from left panel to access next section.

Prefix and Suffix

In this section, we will take the partially matched fragment 'abaab' from previous section as an example, to explain how to utilize prefixes and suffixes to improve algorithm efficiency.

Obviously, if a string is made up of N letters, it will have N-1 prefixes and N-1 suffixes. Let's pair each prefix with same-length-suffix, click Pair to continue.

The longest identical prefix and suffix are 'ab', and its length is 2. That means we can skip the comparison of prefix and suffix with length 4 or 3, cause they are definitely unmatched. Please click Skip to review the improved brute force process.

When we get matched fragment 'abaab' after comparison between substring 3 and pattern; we can skip comparison between substring 4 and pattern, due to from above pair chart, we know prefix and suffix with length 4 are not identical; so does that of substring 5 with prefix and suffix of length 3; once starting to compare substring 6 and pattern, we can directly go to the unmatched index 7.

So once we get matched fragment from one comparison, we can pair the prefix and suffix, find the longest length of matched pair: 2, using unmatched index 7 to deduct that, then 5 is the start index of next substring which should be compared. So it is not necessary to compare each sub-string one letter behind the previous one.

Now, we need to set a table store those information, please press the "PMT" button on left panel to access to the next chapter!

Partial Match Table(PMT)

The pattern string 'abaabcac' could have multiple cases of partial matched fragment when searching occurences in text string. We can caculate the longest length of each case, please click PMT to see all the cases.

So we can record all cases' longest length in a table which is correspond to pattern string. Actually in order to facilitate coding, we will use another table "NEXT" instead, which shifts "PMT" elements one position to the right, and fill "-1" at first index. Click NEXT to see these two tables.

Now we can use 'NEXT' table to skip unecessary comparion, proceeding to next chapter by press left "Animation" button.

Complete Process

Press Animation to initialize/reset the animation.

Press Run to start!

TP: text string pointer
PP: pattern string pointer