การค้นหารูปแบบไร้เดียงสา

การค้นหารูปแบบที่ไร้เดียงสาเป็นวิธีที่ง่ายที่สุดในบรรดาอัลกอริธึมการค้นหารูปแบบอื่นๆ จะตรวจสอบอักขระทั้งหมดของสตริงหลักกับรูปแบบ อัลกอริทึมนี้มีประโยชน์สำหรับข้อความที่มีขนาดเล็กลง ไม่ต้องการขั้นตอนก่อนการประมวลผลใดๆ เราสามารถค้นหาสตริงย่อยได้โดยการตรวจสอบสตริงหนึ่งครั้ง นอกจากนี้ยังไม่ใช้พื้นที่เพิ่มเติมในการดำเนินการ

ความซับซ้อนของเวลาของวิธี Naïve Pattern Search คือ 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)

ป้อนข้อมูล - ข้อความและรูปแบบ

ผลลัพธ์ − ตำแหน่งที่มีรูปแบบอยู่ในข้อความ

Begin
   patLen := pattern Size
   strLen := string size

   for i := 0 to (strLen - patLen), do
      for j := 0 to patLen, do
         if text[i+j] ≠ pattern[j], then
            break the loop
      done

      if j == patLen, then
         display the position i, as there pattern found
   done
End

ตัวอย่าง

#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++) {      //check for each character of pattern if it is matched
         if(mainString[i+j] != pattern[j])
            break;
      }

      if(j == patLen) {     //the pattern is found
         (*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;
   }
}

ผลลัพธ์

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