การค้นหาแพทเทิร์นแบบ Naive (Naive Pattern Searching)

บทนำ

Naive Pattern Searching เป็นวิธีง่ายที่สุดในการค้นหาแพทเทิร์น ตรวจสอบตัวอักษรทุกตัวของข้อความหลักกับแพทเทิร์น เหมาะสำหรับข้อความขนาดเล็ก ไม่ต้องมีขั้นตอน Pre-processing และไม่ใช้พื้นที่เพิ่มเติม

ความซับซ้อนของเวลา (Time Complexity)

O(m × n) โดย m คือขนาดแพทเทิร์น และ n คือขนาดข้อความหลัก

อินพุตและเอาต์พุต

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

อัลกอริทึม

naivePatternSearch(pattern, text)

Input: ข้อความและแพทเทิร์น
Output: ตำแหน่งที่พบแพทเทิร์นในข้อความ

Begin
    patLen := ขนาด pattern
    strLen := ขนาด string
    for i := 0 ถึง (strLen - patLen) do
        for j := 0 ถึง patLen do
            if text[i+j] ≠ pattern[j] then break
        done
        if j == patLen then แสดงตำแหน่ง i
    done
End

ตัวอย่างโค้ด (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

ผลลัพธ์
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18