The KMP Algorithm

Lecture notes:
http://www.cs.cmu.edu/afs/cs/academic/class/15451-f17/www/lectures/lec09-kmp.pdf

In the practical implementation below the data structure that we build
from preprocessing the pattern is all contained in an array of
integers called memo[].  This implementation illustrates the use of
the algorithm for finding all matches of a pattern s in a text t.

public class kmp {
    public static void main(String[] args) {
        char[] s = "test".toCharArray();
        int n = s.length;
        int[] memo = new int[n];
        /*  memo[i] will store the length of the longest prefix of s
            that matches the tail of s1...si */

        int j=0;
        for (int i=1; i<n; i++) {
            while (j>0 && s[i] != s[j]) j = memo[j-1];
            if (s[i] == s[j]) j++;
            memo[i] = j;
        }

        /* Here's another version of the algorithm that computes
        exactly the same thing. */
        /*
        for (int i=1; i<n; i++) {
            int j=i;
            while (j>0 && s[i] != s[memo[j-1]]) j = memo[j-1];
            memo[i] = (j>0) ? memo[j-1]+1 : 0;
        }
        */

        char[] t = "testestest hello there test!".toCharArray();
        int m = t.length;

        j=0;
        for (int i=0; i<m; i++) {
            while (j>0 && t[i] != s[j]) j = memo[j-1];
            if (t[i] == s[j]) j++;
            if (j==n) {
                System.out.println("match found at "+(i-j+1));
                j = memo[j-1];
            }
        }
    }
}    

The first phase of the algorithm computes the memo[] array.
This is a preprocessing step on the pattern, and does not
depend on the text string at all.

The second phase uses the memo array to find all the matches
of the pattern in the text.

The code is tricky to understand given how short it is.

The invariant that holds at the start of the loop is the following:

  memo[k] for all k<i is the following:
  it is the length of the longest prefix of s
  that matches the tail of s1, s2...sk

The goal of one iteration of the outer loop is to compute memo[i].
Let's do an example.  Suppose s is the string "1110111101".

Here is memo:

    i        0   1   2   3   4   5   6   7   8   9
------------------------------------------------------------------
  memo[i]    0   1   2   0   1   2   3   3   4   5

Let's see what this means.  Consider memo[1].

       s1..s1 =   1
       s      =   1110111101

The match is of length 1 so memo[1]=1.

       s1..s2 =   11
       s      =   1110111101

The match is of length 2 so memo[2]=2.

       s1..s3 =   110
       s      =      1110111101   (shifted to show no match)

No match so memo[3]=0

       s1..s4 =   1101
       s      =      1110111101

One match so memo[4]=1.

       s1..s5 =   11011
       s      =      1110111101

Again a match so memo[5]=2.

       s1..s6 =   110111
       s      =      1110111101

Again a match so memo[6]=3.

       s1..s7 =   1101111
       s      =      1110111101    mismatch so shift s over enought to make it match
       s      =       1110111101

This is the key point we need to illustrate the algorithm.

The length of the match is 3 so memo[7]=3.

       s1..s8 =   11011110
       s      =       1110111101

memo[8] = 4.

       s1..s9 =   110111101
       s      =       1110111101

memo[9] = 5.

At this point I have to draw pictures on the blackboard to explain how
it works.

The running time of the algorithm is linear because each iteration of
the inner loop decreases j.  Each iteration of the outer loop
increases i and increases j by at most 1.  Consider the quantity 2i-j.
This increases for every bit of work the algorithm does.  And it is
bounded between 0 and 2m.