素朴なパターン検索

ナイーブパターン検索は、他のパターン検索アルゴリズムの中で最も簡単な方法です。パターンに対するメイン文字列のすべての文字をチェックします。このアルゴリズムは、小さいテキストに役立ちます。前処理フェーズは必要ありません。文字列を1回チェックすることで、部分文字列を見つけることができます。また、操作を実行するための余分なスペースを占有しません。

ナイーブパターン検索法の時間計算量はO（m * n）です。 mはパターンのサイズ、nはメインストリングのサイズです。

入力と出力

Input:
Main String: “ABAAABCDBBABCDDEBCABC”, pattern: “ABC”
Output:
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

アルゴリズム

naivePatternSearch(pattern, text)

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

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

Begin
   patLen := pattern Size
   strLen := string size

   for i := 0 to (strLen - patLen), do
      for j := 0 to patLen, do
         if text[i+j] ≠ pattern[j], then
            break the loop
      done

      if j == patLen, then
         display the position i, as there pattern found
   done
End

例

#include<iostream>
using namespace std;

void naivePatternSearch(string mainString, string pattern, int array[], int *index) {
   int patLen = pattern.size();
   int strLen = mainString.size();

   for(int i = 0; i<=(strLen - patLen); i++) {
      int j;
      for(j = 0; j<patLen; j++) {      //check for each character of pattern if it is matched
         if(mainString[i+j] != pattern[j])
            break;
      }

      if(j == patLen) {     //the pattern is found
         (*index)++;
         array[(*index)] = i;
      }
   }
}

int main() {
   string mainString = "ABAAABCDBBABCDDEBCABC";
   string pattern = "ABC";
   int locArray[mainString.size()];
   int index = -1;
   naivePatternSearch(mainString, pattern, locArray, &index);

   for(int i = 0; i <= index; i++) {
      cout << "Pattern found at position: " << locArray[i]<<endl;
   }
}

出力

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18