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

Cでのパターンマッチング −文字列が別の文字列に存在するかどうかを確認する必要があります。たとえば、文字列「algorithm」は文字列「naivealgorithm」内に存在します。見つかった場合、その場所（つまり、存在する位置）は次のようになります。表示されます。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

ナイーブパターン検索でこの問題を解決しています。このアルゴリズムは、小さいテキストに役立ちます。ナイーブは、ある文字列が別の文字列内のどこにあるかを確認するためのシンプルで非効率的な方法です。文字列が存在する可能性のあるすべての場所を1つずつ調べて、そこにあるかどうかを調べます。

ナイーブアルゴリズムの時間計算量はO（mn）です。ここで、mは検索するパターンのサイズ、nはコンテナ文字列のサイズです。

パターン検索は、コンピュータサイエンスにおいて非常に重要な問題です。メモ帳/単語ファイル、ブラウザ、データベース、または一部の情報で文字列を検索する場合は常に、パターン検索アルゴリズムを使用して検索結果を表示します。

アルゴリズム

naive_algorithm（pattern、text）

入力 −テキストとパターン

出力 −パターンがテキストに存在する場所

Start
   pat_len := pattern Size
   str_len := string size
   for i := 0 to (str_len - pat_len), do
      for j := 0 to pat_len, do
         if text[i+j] ≠ pattern[j], then
         break
   if j == patLen, then
   display the position i, as there pattern found
End

例

#include <stdio.h>
#include <string.h>
int main (){
   char txt[] = "tutorialsPointisthebestplatformforprogrammers";
   char pat[] = "a";
   int M = strlen (pat);
   int N = strlen (txt);
   for (int i = 0; i <= N - M; i++){
      int j;
      for (j = 0; j < M; j++)
         if (txt[i + j] != pat[j])
      break;
      if (j == M)
         printf ("Pattern matches at index %d \n", i);
   }
   return 0;
}

出力

Pattern matches at 6
Pattern matches at 25
Pattern matches at 39