इस समस्या में, हमें दो स्ट्रिंग्स दी गई हैं: एक टेक्स्ट और एक पैटर्न। हमारा कार्य पैटर्न सर्च के लिए KMP एल्गोरिदम का प्रोग्राम बनाना है, जो टेक्स्ट स्ट्रिंग में पैटर्न की सभी घटनाओं को ढूंढेगा।
हमें टेक्स्ट में पैटर्न की सभी घटनाओं को ढूंढना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
text = "xyztrwqxyzfg" pattern = "xyz"
आउटपुट
Found at index 0 Found at index 7
यहां हम KMP (नुथ-मॉरिस-प्रैट) पैटर्न सर्चिंग एल्गोरिदम का उपयोग करके समस्या के समाधान पर चर्चा करेंगे, यह पैटर्न के एक प्रीप्रोसेस्ड स्ट्रिंग का उपयोग करता है जिसका उपयोग टेक्स्ट में मिलान के लिए किया जाता है। और यह उन मामलों में पैटर्न मिलान खोजने में मदद करता है जहां मिलान करने वाले कैरेक्टर्स के बाद स्ट्रिंग का वह कैरेक्टर आता है जो पैटर्न से मेल नहीं खाता।
हम पैटर्न को प्रीप्रोसेस करके एक ऐरे बनाएंगे जिसमें पैटर्न से उचित प्रीफिक्स और सफिक्स होंगे जो मिसमैच पैटर्न खोजने में मदद करेंगे।
पैटर्न सर्चिंग के लिए KMP एल्गोरिदम प्रोग्राम
// पैटर्न सर्चिंग के लिए KMP एल्गोरिदम प्रोग्राम
उदाहरण
#include#include 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
