kmpMatch  Knuth-Morris-Prattによる文字列照合アルゴリズム
kmpNext   文字列照合のためのシフト表の作成

文字列照合
    char *kmpMatch(char *text, int len, char *pattern,
                   int patlen, int *next);
シフト表の作成
    int kmpNext(int *next, int nlen, char *pattern, int patlen);

文字列照合関数において
    text     （入力）テキスト
    len      （入力）テキストの長さ
    pattern  （入力）照合パターン
    patlen   （入力）照合パターンの長さ
    next     （入力）シフト表

シフト表の作成関数において
    next     （入出力）シフト表
    nlen     （入力）　next配列の長さ
    pattern  （入力）　照合パターン
    patlen   （入力）　照合パターンの長さ

文字列照合関数について
    照合パターンがテキストから見つかった場合はそのポインタ、
    見つからなかった場合は 0 (NULL)。

シフト表の作成関数について
    シフト表を正常に作成できた場合は 0、失敗した場合は -1。

kmpNext() を呼び出してシフト表を作成した後、文字列照合関数
kmpMatch() を利用すること。

char *kmpMatch(char *text, int len, char *pattern, int patlen, int *next)
{
    char *pp;
    char *textEnd, *patEnd;

    if (len < patlen) return NULL;

    textEnd = text + len;
    patEnd  = pattern + patlen;

    pp = pattern;
    while (text != textEnd) {
        if (*text++ == *pp) pp++;
        else if (pp != pattern) {
            pp = pattern + *(next + (pp - pattern));
            text--;
        }
        if (pp == patEnd) return text - patlen;
    }

    return NULL;
}

int kmpNext(int *next, int nlen, char *pattern, int patlen)
{
    char *tp, *pp;
    char *patEnd;

    if (nlen < patlen) return -1;

    patEnd  = pattern + patlen;
    *next = 0;

    tp = pp = pattern;
    while (++tp != patEnd) {
        *(next + (tp - pattern)) = pp - pattern;
        if (*tp == *pp) pp++;
    }

    return 0;
}

文字列照合の速度を上げるには、一致する、または一致しないこと がわかっている無駄な比較をできるだけ避けることが望ましい。そのため には、照合を始める前に準備をしておくことが必要である。すなわち、k 文字だけ一致した後で不一致が見つかったときに、テキストのどの文字と パターンのどの文字の比較から照合を続ければよいかをあらかじめ調べて おく。不一致となった位置から左側k文字がわかっていることを利用して、 無駄な比較を避けるように設定するのである。これを表の形で記録する。 このシフト表を求める計算においては、調べる対象はパターンのみである。

KMPアルゴリズムの比較回数は、最大 2n 回である。つまり計算量は O(n) である。ただし、n はテキストの長さを表す。

しかし、BM法による文字列照合アルゴリズム に比べると、実用上の性能で劣る。