Tìm mẫu Naive (Naive Pattern Searching)

Giới thiệu

Tìm mẫu Naive là phương pháp đơn giản nhất. Nó kiểm tra từng ký tự của văn bản với mẫu. Phù hợp cho văn bản nhỏ, không cần tiền xử lý, không tốn bộ nhớ thêm.

Độ phức tạp: O(m * n), với m là độ dài mẫu, n là độ dài văn bản.

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

Đầu vào: Văn bản: "ABAAABCDBBABCDDEBCABC", Mẫu: "ABC"
Đầu ra: 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í mẫu xuất hiện trong văn bản

Begin
  patLen := kích thước pattern, strLen := kích thước string
  với i := 0 đến (strLen - patLen) làm:
    với j := 0 đến patLen làm:
      nếu text[i+j] ≠ pattern[j] thì break
    done
    nếu j == patLen thì hiển thị vị trí i
  done
End

Ví dụ (C++)

#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++) {
      if(mainString[i+j] != pattern[j]) break;
    }
    if(j == patLen) {
      (*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;
  }
}

Kết quả đầu ra

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