Tìm kiếm mẫu ngây thơ

Tìm kiếm mẫu đơn giản là phương pháp đơn giản nhất trong số các thuật toán tìm kiếm mẫu khác. Nó kiểm tra tất cả các ký tự của chuỗi chính đối với mẫu. Thuật toán này rất hữu ích cho các văn bản nhỏ hơn. Nó không cần bất kỳ giai đoạn xử lý trước nào. Chúng ta có thể tìm thấy chuỗi con bằng cách kiểm tra chuỗi một lần. Nó cũng không chiếm thêm không gian để thực hiện thao tác.

Độ phức tạp về thời gian của phương pháp Naïve Pattern Search là O (m * n). M là kích thước của mẫu và n là kích thước của chuỗi chính.

Đầu vào và Đầu ra

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

Thuật toán

naivePatternSearch(pattern, text)

Đầu vào - Văn bản và mẫu

Đầu ra - vị trí, nơi các mẫu hiện diện trong văn bản

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

Ví dụ

#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;
   }
}

Đầu ra

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