C Chương trình cho thuật toán Naive để tìm kiếm mẫu

Đối sánh mẫu trong C - Chúng ta phải tìm xem một chuỗi có xuất hiện trong một chuỗi khác hay không, ví dụ như chuỗi "thuật toán" có trong chuỗi "thuật toán ngây thơ". Nếu nó được tìm thấy, thì vị trí của nó (tức là vị trí mà nó hiện diện) là hiển thị. Chúng tôi có xu hướng tạo một hàm nhận 2 mảng ký tự và trả về vị trí nếu khớp xảy ra nếu không sẽ trả về -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

Chúng tôi đang giải quyết vấn đề này với tính năng Tìm kiếm mẫu Naive. Thuật toán này rất hữu ích cho các văn bản nhỏ hơn. Ngây thơ là một cách đơn giản và không hiệu quả để xem bất cứ nơi nào mà một chuỗi xuất hiện trong chuỗi khác là kiểm tra từng vị trí mà nó có thể ở, từng cái một, để kiểm tra xem nó có ở đó hay không.

Độ phức tạp về thời gian của Thuật toán Naive là O (mn), trong đó m là kích thước của mẫu được tìm kiếm và n là kích thước của chuỗi vùng chứa.

Tìm kiếm mẫu là một vấn đề rất quan trọng trong khoa học máy tính. Bất cứ khi nào chúng tôi tìm kiếm một chuỗi trong tệp notepad / word hoặc trình duyệt hoặc cơ sở dữ liệu hoặc trong một số thông tin, các thuật toán tìm kiếm mẫu được sử dụng để hiển thị kết quả tìm kiếm.

Thuật toán

nm_algorithm (mẫu, văn bản)

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

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

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

Ví dụ

#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 \n", i);
   }
   return 0;
}

Đầu ra

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