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

この問題は、単純モード検索によって解決されています。このアルゴリズムは、テキストが小さい場合に役立ちます。 Naive は、文字列が存在する可能性があるすべての位置をチェックして、その文字列が存在するかどうかを確認することで、その文字列が別の文字列内のどこに出現するかを確認する単純かつ非効率的な方法です。

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

パターン検索は、コンピューター サイエンスにおいて非常に重要な問題です。メモ帳やワード ファイル、ブラウザ、データベース、または何らかの情報で文字列を探すときは常に、 検索結果の表示にはパターン検索アルゴリズムが使用されます。

アルゴリズム

naive_algorithm(パターン、テキスト)

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

出力-テキスト内のパターンが出現する場所

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 </p><p>", i);
   }
   return 0;
}

出力

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

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