প্যাটার্ন অনুসন্ধানের জন্য ন্যাভ অ্যালগরিদমের জন্য সি প্রোগ্রাম

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 Pattern Searching এর মাধ্যমে এই সমস্যার সমাধান করছি। এই অ্যালগরিদম ছোট টেক্সট জন্য দরকারী. নিষ্পাপ হল একটি সহজ এবং অকার্যকর উপায় যেখানে একটি স্ট্রিং অন্যটির মধ্যে যেখানেই ঘটবে তা দেখার জন্য একটি একটি করে প্রতিটি জায়গায় পরীক্ষা করা, এটি সেখানে আছে কিনা তা পরীক্ষা করা৷

নেভ অ্যালগরিদমের সময় জটিলতা হল O(mn), যেখানে m হল অনুসন্ধান করা প্যাটার্নের আকার এবং n হল কন্টেইনার স্ট্রিংয়ের আকার৷

কম্পিউটার বিজ্ঞানে প্যাটার্ন অনুসন্ধান একটি অত্যন্ত গুরুত্বপূর্ণ সমস্যা। যখনই আমরা নোটপ্যাড/ওয়ার্ড ফাইল বা ব্রাউজার বা ডাটাবেসে বা কোনো তথ্যে কোনো স্ট্রিং খুঁজি, অনুসন্ধানের ফলাফল দেখানোর জন্য প্যাটার্ন সার্চিং অ্যালগরিদম ব্যবহার করা হয়।

অ্যালগরিদম

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