इस समस्या में, हमें दो स्ट्रिंग्स एक टेक्स्ट और एक पैटर्न दिया जाता है। हमारा काम पैटर्न खोज के लिए केएमपी एल्गोरिदम के लिए एक प्रोग्राम बनाना है, यह टेक्स्ट स्ट्रिंग में पैटर्न की सभी घटनाओं को ढूंढेगा।
यहां, हमें टेक्स्ट में पैटर्न की सभी घटनाओं का पता लगाना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
text = “xyztrwqxyzfg” pattern = “xyz”
आउटपुट
Found at index 0 Found at index 7
यहां, हम केएमपी (नुथ मॉरिस प्रैट . का उपयोग करके समस्या के समाधान पर चर्चा करेंगे ) पैटर्न खोज एल्गोरिदम, यह पैटर्न के प्रीप्रोसेसिंग स्ट्रिंग का उपयोग करेगा जिसका उपयोग टेक्स्ट में मिलान के लिए किया जाएगा। और उस मामले में पैटर्न मिलान को संसाधित करने या खोजने में मदद करता है जहां मिलान करने वाले वर्णों के बाद स्ट्रिंग के वर्ण का अनुसरण किया जाता है जो पैटर्न से मेल नहीं खाता है।
हम एक सरणी बनाने के लिए पैटर्न वैंड को प्रीप्रोसेस करेंगे जिसमें पैटर्न से उचित उपसर्ग और प्रत्यय शामिल हैं जो बेमेल पैटर्न को खोजने में मदद करेंगे।
पैटर्न खोज के लिए KMP एल्गोरिथम के लिए प्रोग्राम
// पैटर्न खोज के लिए केएमपी एल्गोरिथम के लिए सी प्रोग्राम
उदाहरण
#include<iostream>
#include<string.h>
using namespace std;
void prefixSuffixArray(char* pat, int M, int* pps) {
int length = 0;
pps[0] = 0;
int i = 1;
while (i < M) {
if (pat[i] == pat[length]) {
length++;
pps[i] = length;
i++;
} else {
if (length != 0)
length = pps[length - 1];
else {
pps[i] = 0;
i++;
}
}
}
}
void KMPAlgorithm(char* text, char* pattern) {
int M = strlen(pattern);
int N = strlen(text);
int pps[M];
prefixSuffixArray(pattern, M, pps);
int i = 0;
int j = 0;
while (i < N) {
if (pattern[j] == text[i]) {
j++;
i++;
}
if (j == M) {
printf("Found pattern at index %d\n", i - j);
j = pps[j - 1];
}
else if (i < N && pattern[j] != text[i]) {
if (j != 0)
j = pps[j - 1];
else
i = i + 1;
}
}
}
int main() {
char text[] = "xyztrwqxyzfg";
char pattern[] = "xyz";
printf("The pattern is found in the text at the following index : \n");
KMPAlgorithm(text, pattern);
return 0;
} आउटपुट
पाठ में पैटर्न निम्न अनुक्रमणिका पर पाया जाता है -
Found pattern at index 0 Found pattern at index 7