KMP

KMP (Knuth–Morris–Pratt)

KMP was a milestone: it established a string-matching algorithm with linear worst-case running time. BM and Sunday can also reduce comparisons, but their worst-case time cannot generally be described as linear.

The algorithm was proposed by D. E. Knuth, J. H. Morris and V. R. Pratt. Its name consists of the initials of their surnames.

Like BM, KMP reduces unnecessary character comparisons, but focuses on the prefix that has already matched.

During one matching attempt, it is possible to infer that several later alignments cannot succeed. The core idea is to skip those impossible attempts and reduce comparisons.

For example, GTG at the end of the matched text is the longest matching suffix, and GTG at the start of the pattern is the longest matching prefix.

Align this longest matching suffix with the longest matching prefix.

After another mismatch, G at the end of the matched text is the longest matching suffix, and G at the pattern's start is the longest matching prefix.

Align these two substrings again.

KMP finds the longest matching proper prefix and suffix of the part that has already matched, then aligns them in the next attempt to shift the pattern efficiently.

How do we find these substrings for every pattern prefix? Must we scan them again each time?

There is no need to repeat the scan each time. Cache the results in advance and retrieve them when needed. This cache is called the next array; constructing it is the most difficult part of KMP.

The next array

next[i] is the largest k such that the first k characters of P[0] through P[i] equal its last k characters. k cannot be i + 1: that would compare the whole substring with itself and convey no useful information.

For example, S = "ABABAABAABAC" and P = "ABAABAC".

After three characters match, next[3−1] = 1 gives a longest border of length 1. Shift by the matched length minus the border length: 3 − 1 = 2.

After six characters match, next[6−1] = 3 gives a border of length 3. Shift by 6 − 3 = 3.

After skipping impossible alignments, comparison resumes at the previous text mismatch, rather than restarting from the beginning.

Algorithm analysis

Let m be the pattern length and n the text length. The only extra storage is the next array, so space complexity is $O(m)$.

The algorithm has two phases. Building next takes $O(m)$ time; scanning the text takes $O(n)$. Total time is therefore $O(m+n)$.

KMP

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int *get_nexts(const char *p) {
    int n = strlen(p);
    int *next = (int *)malloc(sizeof(int) * n);
    memset(next, 0, sizeof(int) * n);
    int j = 0;

    for (int i = 1; i < n; i++) {
        while (j != 0 && p[j] != p[i]) {
            j = next[j - 1];
        }
        if (p[j] == p[i]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

int kmp(const char *s, const char *p) {
    if (p[0] == '\0') {
        return 0;
    }
    int *next = get_nexts(p);
    int j = 0;
    int s_len = strlen(s);
    int p_len = strlen(p);

    for (int i = 0; i < s_len; i++) {
        while (j > 0 && s[i] != p[j]) {
            j = next[j - 1];
        }
        if (s[i] == p[j]) {
            j++;
        }
        if (j == p_len) {
            free(next);
            return i - p_len + 1;
        }
    }

    free(next);
    return -1;
}

int main(void) {
    const char *s = "GTGTGAGCTGGTGTGTGCFAA";
    const char *p = "GTGTGCF";
    printf("%d\n", kmp(s, p));
    return 0;
}

Return the start index of the first full match, or −1 if no match exists. An empty pattern returns 0. C/C++ operate on bytes, Java on UTF-16 code units, and Python on characters; these examples use ASCII.