C言語で学ぶラビン-カープ（Rabin-Karp）アルゴリズムによるパターン検索

C言語におけるパターンマッチングとは、ある文字列が別の文字列の中に存在するかどうかを調べる処理のことです。例えば、「algorithm」という文字列が「naive algorithm」という文字列の中に含まれているかを検索し、見つかった場合はその位置（インデックス）を表示します。ここでは、2つの文字配列を受け取り、一致が見つかればその位置を返し、見つからなければ -1 を返す関数を作成します。

入力例1：
txt = "HERE IS A NICE CAP"
pattern = "NICE"
出力：パターンがインデックス10で見つかりました

入力例2：
txt = "XYZXACAADXYZXYZX"
pattern = "XYZX"
出力：パターンがインデックス0で見つかりました
　　　パターンがインデックス9で見つかりました
　　　パターンがインデックス12で見つかりました

ラビン-カープ（Rabin-Karp）アルゴリズムとは

ラビン-カープアルゴリズムは、Michael O. Rabin と Richard M. Karp によって提案された文字列照合アルゴリズムで、より効率的にパターンを検索することを目的としています。単純なナイーブ法（全探索）と同様に、検索窓（ウィンドウ）を1文字ずつずらしながらパターンとの一致を確認しますが、その際にすべての文字を毎回比較するのではなく、ハッシュ値を活用する点が大きな特徴です。

まずテキスト側の部分文字列とパターンのハッシュ値を計算し、ハッシュ値が一致した場合にのみ、実際に1文字ずつの詳細な比較を行います。これにより、テキストの各部分文字列に対して原則1回の比較で済むため、パターン検索を効率化できます。

• 前処理時間：O(m)
• 平均時間計算量：O(m + n)
• 最悪時間計算量：O(mn)（ハッシュ値の衝突が多発するケース）

ここで、m はパターンの長さ、n はテキストの長さを表します。

アルゴリズムの手順

rabinkarp_algo(text, pattern, prime)

入力： 検索対象となる本文（text）とパターン（pattern）、およびハッシュ値の計算に用いる素数（prime）

出力： パターンが見つかった位置の一覧

Start
　pat_len := パターンの長さ
　str_len := 文字列の長さ
　patHash := 0、strHash := 0、h := 1
　maxChar := 文字セットに含まれる文字の総数
パターン内の全文字について i をループ：
　h := (h * maxChar) mod prime
パターン内の全文字インデックス i についてループ：
　patHash := (maxChar * patHash + pattern[i]) mod prime
　strHash := (maxChar * strHash + text[i]) mod prime
i := 0 から (str_len - pat_len) までループ：
　if patHash = strHash ならば
　　charIndex := 0 から pat_len - 1 までループ：
　　　if text[i + charIndex] ≠ pattern[charIndex] ならば break
　if charIndex = pat_len ならば
　　位置 i にパターンが見つかったことを出力
　if i < (str_len - pat_len) ならば
　　strHash := (maxChar * (strHash - text[i] * h) + text[i + patLen]) mod prime
　　if strHash < 0 ならば
　　　strHash := strHash + prime
End

C言語での実装例

以下は、ラビン-カープアルゴリズムをC言語で実装したサンプルプログラムです。基数 d には256（ASCII文字セットのサイズ）を使用しています。

#include<stdio.h>
#include<string.h>
int main () {
   char txt[80], pat[80];
   int q;
   printf ("Enter the container string \n");
   scanf ("%s", &txt);
   printf ("Enter the pattern to be searched \n");
   scanf ("%s", &pat);
   int d = 256;
   printf ("Enter a prime number \n");
   scanf ("%d", &q);
   int M = strlen (pat);
   int N = strlen (txt);
   int i, j;
   int p = 0;
   int t = 0;
   int h = 1;
   for (i = 0; i < M - 1; i++)
      h = (h * d) % q;
   for (i = 0; i < M; i++){
      p = (d * p + pat[i]) % q;
      t = (d * t + txt[i]) % q;
   }
   for (i = 0; i <= N - M; i++){
      if (p == t){
         for (j = 0; j < M; j++){
            if (txt[i + j] != pat[j])
            break;
         }
         if (j == M)
            printf ("Pattern found at index %d \n", i);
      }
      if (i < N - M){
         t = (d * (t - txt[i] * h) + txt[i + M]) % q;
         if (t < 0)
            t = (t + q);
      }
   }
   return 0;
}

実行結果

Enter the container string
tutorialspointisthebestprogrammingwebsite
Enter the pattern to be searched
p
Enter a prime number
3
Pattern found at index 8
Pattern found at index 21

この実行例では、長い文字列の中から文字「p」を検索しており、インデックス8と21の2箇所でパターンが見つかったことが確認できます。ハッシュ値が一致した位置でのみ詳細な文字比較を行うため、大量のテキストからパターンを検索する場面で特に有効なアルゴリズムです。