โปรแกรม C สำหรับ Naive Algorithm ในการค้นหาแพทเทิร์น

Pattern matching ใน C - หาว่าสตริงหนึ่งอยู่ในอีกสตริงหนึ่งหรือไม่ เช่น "algorithm" อยู่ใน "naive algorithm" หากเจอ แสดงตำแหน่ง (index)

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: วิธีง่ายและไม่ประหยัดสำหรับข้อความเล็ก ตรวจสอบทุกตำแหน่งที่เป็นไปได้ทีละตัว

Time complexity: O(mn) โดย m = ขนาดแพทเทิร์น n = ขนาดข้อความ

Pattern searching สำคัญในวิทยาการคอมพิวเตอร์: ค้นหาใน notepad, browser, database

อัลกอริทึม

naive_algorithm(pattern, text):
    pat_len = pattern size
    str_len = string size
    for i = 0 to (str_len - pat_len):
        for j = 0 to pat_len:
            if text[i+j] != pattern[j]: break
        if j == patLen: แสดงตำแหน่ง i

ตัวอย่างโค้ด

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

เอาต์พุต

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