パターン検索のためのKMPアルゴリズムのCプログラム

この問題では、テキストとパターンの2つの文字列が与えられます。私たちのタスクは、パターン検索用のKMPアルゴリズムのプログラムを作成することです。これにより、テキスト文字列内のパターンのすべての出現箇所が検出されます。

ここでは、テキスト内のパターンのすべての出現を見つける必要があります。

問題を理解するために例を見てみましょう

入力

text = “xyztrwqxyzfg” pattern = “xyz”

出力

Found at index 0
Found at index 7

ここでは、KMP（ Knuth Morris Pratt ）を使用した問題の解決策について説明します。 ）パターン検索アルゴリズム。テキストの照合に使用されるパターンの前処理文字列を使用します。また、一致する文字の後にパターンと一致しない文字列の文字が続く場合に、パターンの一致を処理または検索するのに役立ちます。

パターンワンドを前処理して、パターンから適切なプレフィックスとサフィックスを含む配列を作成します。これは、不一致パターンの検索に役立ちます。

パターン検索のためのKMPアルゴリズムのプログラム

//パターン検索用のKMPアルゴリズムのCプログラム

例

#include<iostream>
#include<string.h>
using namespace std;
void prefixSuffixArray(char* pat, int M, int* pps) {
   int length = 0;
   pps[0] = 0;
   int i = 1;
   while (i < M) {
      if (pat[i] == pat[length]) {
         length++;
         pps[i] = length;
         i++;
      } else {
         if (length != 0)
         length = pps[length - 1];
         else {
            pps[i] = 0;
            i++;
         }
      }
   }
}
void KMPAlgorithm(char* text, char* pattern) {
   int M = strlen(pattern);
   int N = strlen(text);
   int pps[M];
   prefixSuffixArray(pattern, M, pps);
   int i = 0;
   int j = 0;
   while (i < N) {
      if (pattern[j] == text[i]) {
         j++;
         i++;
      }
      if (j == M) {
         printf("Found pattern at index %d\n", i - j);
         j = pps[j - 1];
      }
      else if (i < N && pattern[j] != text[i]) {
         if (j != 0)
         j = pps[j - 1];
         else
         i = i + 1;
      }
   }
}
int main() {
   char text[] = "xyztrwqxyzfg";
   char pattern[] = "xyz";
   printf("The pattern is found in the text at the following index : \n");
   KMPAlgorithm(text, pattern);
   return 0;
}

出力

このパターンは、テキストの次のインデックスにあります-

Found pattern at index 0
Found pattern at index 7