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 を選べば実用上その問題 を無視してよい。