KMP Explained

Unless you participated in informatics competitions, you probably first encountered this algorithm in a data structures class. Given the uneven teaching quality and sometimes frustrating explanations in university computer science departments, many students leave confused. Here is my detailed explanation; I hope it helps.

The next Array

The next array is the core of KMP. For each p[1..j], it records the maximum length of an equal proper prefix and suffix.

A useful detail: I recommend indexing the two strings from 1, because j then directly represents the first j characters without another offset calculation. For example, with the pattern p = "abcabx", we have p[1]='a', p[2]='b', and so on through p[6]='x'. Then next[5] directly describes the longest matching prefix and suffix of the first five characters, abcab: its value is 2. The logic is clear.

Diagram 1 Diagram 2

The diagrams show what the array means. The first A has no matching proper prefix and suffix, so its value is 0. The second character B is likewise 0. The third character A matches the initial A, giving 1. AB matches the initial AB, giving length 2. C has no match, giving 0. Thus next[4] = 2, and the pattern can move forward by two positions.

This illustrates KMP’s advantage. On encountering a mismatch, it uses what we already know about the successfully matched characters instead of backtracking through the main string as brute force does. The main-string pointer does not retreat, reducing the time complexity from O(n*m) to O(n+m).

Computing the next Array

for (int i = 2, j = 0; i <= m; i++) {
    while (j > 0 && p.charAt(i) != p.charAt(j + 1)) {
        j = next[j];
    }
    if (p.charAt(i) == p.charAt(j + 1)) {
        j++;
    }
    next[i] = j;
}

Let us walk through the example above. The array has length m + 1. Here the pattern length is 5, so the array size is 6.

i starts at 2: the first character is at index 1, and next[1] is always 0, so computation begins with the second character. j starts at 0.

First iteration: i = 2, computing next[2]. Compare p.charAt(2), B, with p.charAt(j + 1), which is p.charAt(1), A. They differ, but j = 0, so the while condition fails. No match follows, j remains 0, and next[2] = 0.

Second iteration: i = 3, computing next[3]. Compare p.charAt(3), A, with p.charAt(1), A. They match, so increment j to 1 and set next[3] = 1.

Third iteration: i = 4, computing next[4]. Compare p.charAt(4), B, with p.charAt(2), B. They match, so j becomes 2 and next[4] = 2, consistent with the diagram.

Fourth iteration: i = 5, computing next[5]. Compare p.charAt(5), C, with p.charAt(3), A. They differ and j = 2 > 0, so enter the while loop and set j = next[j] = next[2] = 0. Compare C with p.charAt(1), A; they still differ. Since j is now 0, the loop ends. No match follows, so next[5] = 0.

Matching the Pattern in the Main String

for (int i = 1, j = 0; i <= n; i++) {
    while (j > 0 && s.charAt(i) != p.charAt(j + 1)) {
        j = next[j];
    }
    if (s.charAt(i) == p.charAt(j + 1)) {
        j++;
    }
    if (j == m) {
        return i - m; // The one-based start is i-m+1; return a zero-based index.
    }
}

Iteration 1:

// 1. j=0, so the mismatch-backtracking loop does not run.
while (j > 0 && s.charAt(1) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. s[1]='A' matches p[1]='A'; j becomes 1.
if (s.charAt(1) == p.charAt(j + 1)) {
    j++;
}
// 3. j=1 is not 7, so no return yet.
if (j == m) {
    return i - m;
}

Iteration 2:

// 1. j=1>0, but s[2]='B' matches p[2]='B'; skip the loop.
while (j > 0 && s.charAt(2) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. The characters match; j becomes 2.
if (s.charAt(2) == p.charAt(j + 1)) {
    j++;
}
// 3. j=2 is not 7.
if (j == m) {
    return i - m;
}

Iteration 3:

// 1. j=2>0, but s[3]='A' matches p[3]='A'; skip the loop.
while (j > 0 && s.charAt(3) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. The characters match; j becomes 3.
if (s.charAt(3) == p.charAt(j + 1)) {
    j++;
}
// 3. j=3 is not 7.
if (j == m) {
    return i - m;
}

Iteration 4:

// 1. j=3>0, but s[4]='B' matches p[4]='B'; skip the loop.
while (j > 0 && s.charAt(4) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. The characters match; j becomes 4.
if (s.charAt(4) == p.charAt(j + 1)) {
    j++;
}
// 3. j=4 is not 7.
if (j == m) {
    return i - m;
}

Iteration 5:

// 1. j=4>0 and s[5]='A' differs from p[5]='C'; fall back.
while (j > 0 && s.charAt(5) != p.charAt(j + 1)) {
    j = next[j]; // next[4]=2, so j becomes 2.
}
// 2. Now s[5]='A' matches p[3]='A'; j becomes 3.
if (s.charAt(5) == p.charAt(j + 1)) {
    j++;
}
// 3. j=3 is not 7.
if (j == m) {
    return i - m;
}

Iteration 6:

// 1. j=3>0, but s[6]='B' matches p[4]='B'; skip the loop.
while (j > 0 && s.charAt(6) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. The characters match; j becomes 4.
if (s.charAt(6) == p.charAt(j + 1)) {
    j++;
}
// 3. j=4 is not 7.
if (j == m) {
    return i - m;
}

Iteration 7:

// 1. j=4>0, but s[7]='C' matches p[5]='C'; skip the loop.
while (j > 0 && s.charAt(7) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. The characters match; j becomes 5.
if (s.charAt(7) == p.charAt(j + 1)) {
    j++;
}
// 3. j=5 is not 7.
if (j == m) {
    return i - m;
}

Iteration 8:

// 1. j=5>0, but s[8]='A' matches p[6]='A'; skip the loop.
while (j > 0 && s.charAt(8) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. The characters match; j becomes 6.
if (s.charAt(8) == p.charAt(j + 1)) {
    j++;
}
// 3. j=6 is not 7.
if (j == m) {
    return i - m;
}

Iteration 9:

// 1. j=6>0, but s[9]='B' matches p[7]='B'; skip the loop.
while (j > 0 && s.charAt(9) != p.charAt(j + 1)) {
    j = next[j];
}
// 2. The characters match; j becomes 7.
if (s.charAt(9) == p.charAt(j + 1)) {
    j++;
}
// 3. j=7 equals m=7. Return i-m=9-7=2.
if (j == m) {
    return i - m;
}

The final result is 2: the zero-based starting index in the original main string ABABABCABA. The successful match begins at its third character.