C में पैटर्न मिलान - हमें यह ढूंढना है कि कोई स्ट्रिंग दूसरी स्ट्रिंग में मौजूद है या नहीं, उदाहरण के लिए, स्ट्रिंग "algorithm" स्ट्रिंग "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
हम इस समस्या को नाइव पैटर्न सर्चिंग के साथ हल कर रहे हैं। यह एल्गोरिदम छोटे टेक्स्ट के लिए उपयोगी है। नाइव एक सरल और अकुशल तरीका है यह देखने के लिए कि एक स्ट्रिंग दूसरी के भीतर कहां होती है, हर उस स्थान की जांच करके जहां यह हो सकती है, एक-एक करके, यह देखने के लिए कि क्या यह वहां है।
नाइव एल्गोरिदम की समय जटिलता O(mn) है, जहां m खोजे जाने वाले पैटर्न का आकार है और n कंटेनर स्ट्रिंग का आकार है।
पैटर्न खोज कंप्यूटर विज्ञान में एक बहुत महत्वपूर्ण समस्या है। जब भी हम नोटपैड/वर्ड फाइल या ब्राउज़र या डेटाबेस या किसी जानकारी में किसी स्ट्रिंग की खोज करते हैं, तो खोज परिणाम दिखाने के लिए पैटर्न खोज एल्गोरिदम का उपयोग किया जाता है।
एल्गोरिदम
naive_algorithm(pattern, text)
इनपुट - टेक्स्ट और पैटर्न
आउटपुट - वे स्थान जहां पैटर्न टेक्स्ट में मौजूद है
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
