rkMatch  라빈-카프에 의한 캐릭터 라인 조합 알고리즘
rkHash   조합 패턴의 해쉬 함수치

캐릭터 라인 조합
    char *rkMatch(char *text, int len, int patlen,
          unsigned long patHash, unsigned long dm);

조합 패턴의 해쉬 함수치
    unsigned long rkHash(unsigned long *dm, char *pattern, int patlen);

캐릭터 라인 조합 함수에 대해
    text     (입력) 텍스트
    len      (입력) 텍스트의 길이
    patlen   (입력) 조합 패턴의 길이
    patHash  (입력) 조합 패턴의 해쉬 함수치
    dm       (입력) 256m-1 % q 의 값

조합 패턴의 해쉬 함수치의 함수에 대해
    dm       (입출력) 256m-1 % q 의 값
    pattern  (입력) 조합 패턴
    patlen   (입력) 조합 패턴의 길이

캐릭터 라인 조합 함수에 대해
    조합 패턴이 텍스트로부터 발견되었을 경우는 그 포인터,
    발견되지 않았던 경우는 0 (NULL).

조합 패턴의 해쉬 함수치의 함수에 대해
    조합 패턴의 해쉬 함수치

rkPattern()를 호출해 조합 패턴의 해쉬 함수치를 산출한 후,
캐릭터 라인 조합 함수 rkMatch()를 이용하는 것.

#define Q     33554393L   /* prime number */
#define LOG2D 8           /* 2^8 = 256 */

unsigned long rkHash(unsigned long *dm, char *pattern, int patlen)
{
    int      i;
    unsigned long h1;

    for (i = 1, *dm = 1; i < patlen; i++)
        *dm = (*dm << LOG2D) % Q;
    for (i = 0, h1 = 0; i < patlen; i++)
        h1 = ((h1 << LOG2D) + pattern[i]) % Q;
    return h1;
}

char *rkMatch(char *text, int len, int patlen,
     unsigned long patHash, unsigned long dm)
{
    int      i;
    char     *textEnd;
    unsigned long h2;

    if (patlen == 0)  return text;
    if (len < patlen) return NULL;

    for (i = 0, h2 = 0; i < patlen; i++)
        h2 = ((h2 << LOG2D) + text[i]) % Q;

    textEnd = text + (len - patlen) + 1;
    while (text ! = textEnd) {
        if (h2 == patHash) return text;
        h2 = (h2 + (Q << LOG2D) - *text * dm) % Q;
        h2 = ((h2 << LOG2D) + *(text + patlen)) % Q;
        text++;
    }
    return NULL;
}

이 방법에서는 우선 조합 패턴의 해쉬 함수치 h1 를, 다음에 텍스트 최초의 m 문자 분의 해쉬 함수치 h2 를 계산한다. 그 후 텍스트상 의 조합 개시 위치를 오른쪽으로 비켜 놓으면서, 해쉬 함수치를 점화식에 의해 합계 헤아려, 그 값과 h1 와의 비교를 반복한다.

이 방법의 계산량 O(m+n)이다. 다른 캐릭터 라인이 같은 해쉬 함수치를 가진다 (일)것은 이론적으로는 부정할 수 없지만, 큰 소수 q 를 선택하면 실용상 그 문제 (을)를 무시해도 좋다.