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(m)
राबिन-कर्प एल्गोरिदम की समय जटिलता O(m+n) है, लेकिन सबसे खराब स्थिति के लिए यह O(mn) है।
एल्गोरिदम
rabinkarp_algo(text, pattern, prime)
इनपुट - मुख्य टेक्स्ट और पैटर्न। हैश लोकेशन खोजने के लिए एक अभाज्य संख्या।
आउटपुट - वे स्थान जहां पैटर्न मिला।
Start
pat_len := pattern Length
str_len := string Length
patHash := 0 and strHash := 0, h := 1
maxChar := character set में कुल कैरेक्टर्स
pattern के सभी कैरेक्टर के इंडेक्स i के लिए, do
h := (h * maxChar) mod prime
pattern के सभी कैरेक्टर इंडेक्स i के लिए, do
patHash := (maxChar * patHash + pattern[i]) mod prime
strHash := (maxChar * strHash + text[i]) mod prime
for i := 0 to (str_len - pat_len), do
if patHash = strHash, then
for charIndex := 0 to pat_len - 1, do
if text[i + charIndex] ≠ pattern[charIndex], then
break
if charIndex = pat_len, then
print the location i as pattern found at i position.
if i < (str_len - pat_len), then
strHash := (maxChar * (strHash - text[i] * h) + text[i + patLen]) mod prime
if strHash < 0, then
strHash := strHash + prime
End
उदाहरण
#include <stdio.h>
#include <string.h>
int main() {
char txt[80], pat[80];
int q;
printf("कंटेनर स्ट्रिंग दर्ज करें \n");
scanf("%s", txt);
printf("खोजे जाने वाले पैटर्न दर्ज करें \n");
scanf("%s", pat);
int d = 256;
printf("एक अभाज्य संख्या दर्ज करें \n");
scanf("%d", &q);
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0;
int t = 0;
int h = 1;
for (i = 0; i < M - 1; i++)
h = (h * d) % q;
for (i = 0; i < M; i++) {
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
for (i = 0; i <= N - M; i++) {
if (p == t) {
for (j = 0; j < M; j++) {
if (txt[i + j] != pat[j])
break;
}
if (j == M)
printf("Pattern found at index %d \n", i);
}
if (i < N - M) {
t = (d * (t - txt[i] * h) + txt[i + M]) % q;
if (t < 0)
t = (t + q);
}
}
return 0;
}
आउटपुट
Enter the container string tutorialspointisthebestprogrammingwebsite Enter the pattern to be searched p Enter a prime number 3 Pattern found at index 8 Pattern found at index 21
