パターン検索用の Rabin-Karp アルゴリズムの C プログラム

C のパターン マッチング- 文字列が別の文字列内に存在するかどうかを確認する必要があります。たとえば、文字列 "algorithm" が "naive Algorithm" の文字列内に存在するかどうかを確認する必要があります。 」。見つかった場合は、その場所 (つまり、どこにあるか) が表示されます。私たちは 2 文字の配列を受け取り、一致するものがあればその位置を返す関数を作成する傾向があります。 それ以外の場合は、-1 が返されます。

Input: txt = "HERE IS A NICE CAP"
   pattern = "NICE"
Output: Pattern found at index 10
Input: txt = "XYZXACAADXYZXYZX"
   pattern = "XYZX"
Output: Pattern found at index 0
   Pattern found at index 9
   Pattern found at index 12

Rabin-Karp は、別のパターン検索アルゴリズムです。単なる文字列マッチング パターンをより効率的に見つけるために Rabin と Karp によって提案されたアルゴリズム 方法。単純なアルゴリズムと同様に、ウィンドウを移動してパターンをチェックします。 ハッシュを 1 つずつ検索しますが、あらゆる場合にすべての文字をチェックする必要はありません。ハッシュが一致すると、各文字がチェックされます。この方法では、テキスト サブシーケンスごとに比較が 1 回だけ行われるため、より効率的なパターン検索アルゴリズムになります。

前処理時間 - O(m)

Rabin-Karp アルゴリズムの時間計算量は O(m n) ですが、最悪の場合です。 、 O(mn)です。

アルゴリズム

rabinkarp_algo(テキスト、パターン、プライム)

入力

rabinkarp_algo(テキスト、パターン、プライム)

Input Strong>- テキストとパターン。ハッシュ位置で別の素数を見つけます

出力- パターンの位置を見つけます

Start
   pat_len := pattern Length
   str_len := string Length
   patHash := 0 and strHash := 0, h := 1
   maxChar := total number of characters in character set
for index i of all character in the pattern, do
   h := (h*maxChar) mod prime
for all character index i of pattern, do
   patHash := (maxChar*patHash + pattern[i]) mod prime
   strHash := (maxChar*strHash + text[i]) mod prime
for i := 0 to (str_len - pat_len), do
   if patHash = strHash, then
      for charIndex := 0 to pat_len -1, do
         if text[i+charIndex] ≠ pattern[charIndex], then
         break
if charIndex = pat_len, then
   print the location i as pattern found at i position.
if i < (str_len - pat_len), then
   strHash := (maxChar*(strHash &ndash; text[i]*h)+text[i+patLen]) mod prime, then
   if strHash < 0, then
   strHash := strHash + prime
End

Example

ライブ デモンストレーション

#include<stdio.h>
#include<string.h>
int main (){
   char txt[80], pat[80];
   int q;
   printf ("Enter the container string </p><p>");
   scanf ("%s", &txt);
   printf ("Enter the pattern to be searched </p><p>");
   scanf ("%s", &pat);
   int d = 256;
   printf ("Enter a prime number </p><p>");
   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 </p><p>", 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

以上がパターン検索用の Rabin-Karp アルゴリズムの C プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。