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법에 따르는 캐릭터 라인 조합 알고리즘 에 비하면(자), 실용상의 성능으로 뒤떨어진다.