पैटर्न खोज के लिए Naive एल्गोरिथम के लिए सी प्रोग्राम

सी में पैटर्न मिलान - हमें यह पता लगाना है कि क्या कोई स्ट्रिंग किसी अन्य स्ट्रिंग में मौजूद है, उदाहरण के तौर पर, स्ट्रिंग "एल्गोरिदम" स्ट्रिंग "naive algorithm" के भीतर मौजूद है। यदि यह पाया जाता है, तो इसका स्थान (यानी जिस स्थिति में यह मौजूद है) है प्रदर्शित होता है। हम एक ऐसा फ़ंक्शन बनाते हैं जो 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 से हल कर रहे हैं। यह एल्गोरिथम छोटे पाठों के लिए उपयोगी है। Naive यह देखने का एक सरल और अक्षम तरीका है कि एक स्ट्रिंग दूसरे के भीतर कहीं भी होती है, हर जगह की जांच करना, एक-एक करके, यह जांचने के लिए कि क्या यह वहां है।

Naive Algorithm की समय जटिलता 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