C言語で実装するラビン・カープ（Rabin-Karp）アルゴリズムによるパターン検索プログラム

文字列処理の分野において、長いテキストの中から特定のパターンを探し出す「パターンマッチング」は非常に重要な課題です。本記事では、テキスト文字列とパターンの2つの文字列が与えられたとき、ラビン・カープ（Rabin-Karp）アルゴリズムを用いて、テキスト内にパターンが出現するすべての位置（インデックス）を見つけるC言語プログラムを解説します。

問題の定義と具体例

テキスト（text）とパターン（pattern）が与えられ、テキスト中にパターンが出現するすべてのインデックスを出力することが求められます。

入力例

text = "xyztrwqxyzfg"
pattern = "xyz"

出力例

Found at index 0
Found at index 7

この例では、パターン「xyz」はテキストの0番目と7番目の位置に出現しています。

ラビン・カープアルゴリズムの仕組み

ラビン・カープアルゴリズムは、ハッシュ値を活用した効率的な文字列検索手法です。基本的な流れは以下の通りです。

• テキストの中から、パターンと同じ長さの「ウィンドウ」を取り出します。
• このウィンドウを1文字ずつスライドさせながら、各ウィンドウのハッシュ値とパターンのハッシュ値を比較します。
• ハッシュ値が一致した場合のみ、実際に文字同士を1つずつ照合し、本当に一致しているかを確認します（ハッシュ衝突への対策）。

ハッシュ値の計算方法

ラビン・カープ法では、テキストとパターンのハッシュ値の計算が重要になります。ここでは、文字列を構成する各文字の数値（ASCIIコード）を順に加算し、その合計を素数（本プログラムでは103）で割った余りをハッシュ値として使用します。素数で割ることでハッシュ値の範囲が小さく抑えられ、計算も高速になります。

さらに、ウィンドウをスライドさせる際には、先頭の文字の寄与を差し引き、新しく加わる文字の寄与を足すことで、ハッシュ全体を再計算せずにO(1)で更新できる点が大きな特徴です。

C言語による実装

以下が、ラビン・カープアルゴリズムを用いたパターン検索のC言語プログラムです。

#include <stdio.h>
#include <string.h>
#define c 256

void search(char pattern[], char text[]){
    int M = strlen(pattern);
    int N = strlen(text);
    int i, j;
    int hashP = 0;   // パターンのハッシュ値
    int hashT = 0;   // テキストの現在のウィンドウのハッシュ値
    int h = 1;

    // h = 256^(M-1) mod 103 を計算
    for (i = 0; i < M - 1; i++)
        h = (h * c) % 103;

    // パターンとテキスト先頭ウィンドウのハッシュ値を計算
    for (i = 0; i < M; i++) {
        hashP = (c * hashP + pattern[i]) % 103;
        hashT = (c * hashT + text[i]) % 103;
    }

    // ウィンドウを1文字ずつスライドしながら照合
    for (i = 0; i <= N - M; i++) {
        if (hashP == hashT) {
            // ハッシュ一致時は文字単位で確認
            for (j = 0; j < M; j++) {
                if (text[i + j] != pattern[j])
                    break;
            }
            if (j == M)
                printf("Pattern found at index %d \n", i);
        }

        if (i < N - M) {
            // ハッシュ値をローリング方式で更新
            hashT = (c * (hashT - text[i] * h) + text[i + M]) % 103;
            if (hashT < 0)
                hashT = (hashT + 103);  // 負の値になった場合の補正
        }
    }
}

int main(){
    char text[] = "xyztrwqxyzfg";
    char pattern[] = "xyz";
    printf("The pattern is found in the text at the following index : \n");
    search(pattern, text);
    return 0;
}

実行結果

The pattern is found in the text at the following index :
Pattern found at index 0
Pattern found at index 7

まとめ

ラビン・カープアルゴリズムは、平均的にはO(N+M)の時間計算量で動作する効率的な文字列検索アルゴリズムです。最悪の場合はO(N×M)になりますが、ハッシュ値による事前フィルタリングによって不要な文字照合を大幅に減らせる点が魅力です。テキストエディタの検索機能や盗作検出システムなど、さまざまな場面で応用されている手法なので、ぜひ実装を通じて理解を深めてください。