순진한 패턴 검색

순진한 패턴 검색은 다른 패턴 검색 알고리즘 중에서 가장 간단한 방법입니다. 패턴에 대한 기본 문자열의 모든 문자를 확인합니다. 이 알고리즘은 작은 텍스트에 유용합니다. 전처리 단계가 필요하지 않습니다. 문자열을 한 번 확인하여 하위 문자열을 찾을 수 있습니다. 또한 작업을 수행하기 위해 추가 공간을 차지하지 않습니다.

Naive Pattern Search 방법의 시간 복잡도는 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