Chương trình C cho thuật toán Naive tìm mẫu (Pattern Searching)

Tìm mẫu trong chuỗi: kiểm tra chuỗi mẫu có trong chuỗi văn bản không. Ví dụ: "algorithm" trong "naive algorithm". Nếu tìm thấy, hiển thị vị trí.

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, 9, 12

Naive Pattern Searching: cách đơn giản, kém hiệu quả cho văn bản lớn. Kiểm tra từng vị trí có thể có của mẫu trong văn bản.

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

Tìm mẫu là bài toán cốt lõi trong khoa học máy tính: tìm kiếm trong notepad, trình duyệt, cơ sở dữ liệu...

Thuật toán

naive_algorithm(pattern, text):
  pat_len = độ dài pattern
  str_len = độ dài text
  for i = 0 đến str_len - pat_len:
    for j = 0 đến pat_len:
      if text[i+j] != pattern[j]: break
    if j == pat_len: hiển thị vị trí i

Ví dụ mã nguồn

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

Kết quả đầu ra

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