KMP and Its nextval Optimization

KMP is a string-matching algorithm. This note uses the one-based convention commonly seen in 408 exam material:

• Pattern positions begin at 1.
• next[1] = 0.
• For j > 1, next[j] equals one plus the length of the longest equal proper prefix and suffix of the pattern segment before position j.

Some sources use zero-based positions and therefore produce values shifted by one. Both conventions can be correct; do not mix the table from one convention with code written for the other.

Why KMP is needed

Suppose the text is abababcdef and the pattern is ababc. A naive matcher restarts one text position later after every mismatch, repeating comparisons it has already learned from.

KMP keeps the text position and moves the pattern using information encoded in next.

int Index_KMP(SString S, SString T, int next[]) {
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.ch[i] == T.ch[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }

    if (j > T.length) {
        return i - T.length;
    }
    return 0;
}

When j == 0, incrementing j returns it to the first pattern position and incrementing i advances the text.

Prefixes, suffixes, and the next array

• A proper prefix starts at the first character but does not contain the final character of the string.
• A proper suffix ends at the final character but does not contain the first character.

If comparison fails at pattern position j, inspect the substring formed by positions 1 through j - 1. Under this note's convention:

next[j] = longest equal proper-prefix/suffix length + 1
next[1] = 0

For pattern ababaa:

Why is next[6] = 4? Before position 6, the segment is ababa. Its prefixes include a, ab, aba, and abab; its suffixes include a, ba, aba, and baba. The longest equal pair is aba, whose length is 3, so the one-based fallback position is 3 + 1 = 4.

next[2] must be 1 because the segment before position 2 contains only one character and has no non-empty proper prefix/suffix pair. The same reasoning gives next[3] = 1 for segment ab.

The redundant-comparison problem

Consider:

Text:    abcababaa
Pattern: ababaa

If a mismatch occurs at pattern position 3, next[3] = 1. Both pattern positions 3 and 1 contain a. If a at position 3 just failed against the current text character, retrying the same a from position 1 is guaranteed to fail again. That retry is redundant.

Computing nextval

nextval collapses those repeated-character fallback chains:

for (int j = 2; j <= T.length; j++) {
    if (T.ch[next[j]] == T.ch[j]) {
        nextval[j] = nextval[next[j]];
    } else {
        nextval[j] = next[j];
    }
}

For ababaa:

Step by step:

1. At j = 2, T[next[2]] is a and T[2] is b. They differ, so nextval[2] = next[2] = 1.
2. At j = 3, both characters are a. Reuse the optimized fallback from position 1: nextval[3] = nextval[1] = 0.
3. At j = 4, both compared characters are b, so nextval[4] = nextval[2] = 1.
4. Position 5 similarly collapses to 0.
5. At position 6 the characters differ along the fallback, so the value remains 4.

Practice

Compute both arrays for pattern aaaab:

The repeated a fallback chain collapses to zero, while the final b keeps the useful fallback position 4.

For exam questions, first identify the indexing convention, then compute the longest prefix/suffix matches consistently. Once next is correct, nextval follows directly from the character comparison rule.