โปรแกรม C สำหรับอัลกอริธึมไร้เดียงสาสำหรับการค้นหารูปแบบ

การจับคู่รูปแบบในภาษา C − เราต้องค้นหาว่าสตริงมีอยู่ในสตริงอื่นหรือไม่ ตัวอย่างเช่น สตริง "อัลกอริทึม" อยู่ในสตริง "อัลกอริทึมไร้เดียงสา" หากพบ แสดงว่าตำแหน่งของสตริงนั้น (เช่น ตำแหน่งของมันอยู่ที่) แสดงผล เรามักจะสร้างฟังก์ชันที่ได้รับอาร์เรย์อักขระ 2 ตัวและส่งคืนตำแหน่งหากการจับคู่เกิดขึ้นมิฉะนั้นจะคืนค่า -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

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

ความซับซ้อนของเวลาของ Naive Algorithm คือ O(mn) โดยที่ m คือขนาดของรูปแบบที่จะค้นหา และ n คือขนาดของสตริงคอนเทนเนอร์

การค้นหารูปแบบเป็นปัญหาที่สำคัญมากในวิทยาการคอมพิวเตอร์ เมื่อใดก็ตามที่เราค้นหาสตริงในไฟล์ notepad/word หรือเบราว์เซอร์หรือฐานข้อมูลหรือในข้อมูลบางอย่าง อัลกอริธึมการค้นหารูปแบบจะใช้เพื่อแสดงผลการค้นหา

อัลกอริทึม

naive_algorithm(รูปแบบ ข้อความ)

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

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

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

ตัวอย่าง

#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