C-তে প্যাটার্ন ম্যাচিং (Pattern Matching) − আমাদের চেক করতে হবে একটি স্ট্রিং অন্য একটি স্ট্রিংয়ে উপস্থিত কিনা, উদাহরণস্বরূপ, স্ট্রিং "algorithm" স্ট্রিং "naive algorithm" এর মধ্যে উপস্থিত। যদি পাওয়া যায়, তবে তার লোকেশন (অর্থাৎ কোন পজিশনে আছে) ডিসপ্লে করা হয়। আমরা একটি ফাংশন তৈরি করি যা দুটি ক্যারেক্টার অ্যারে নেয় এবং ম্যাচ হলে পজিশন রিটার্ন করে অন্যথায় -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
রাবিন-কার্প (Rabin-Karp) আর একটি প্যাটার্ন সার্চিং অ্যালগরিদম। এটি একটি স্ট্রিং ম্যাচিং অ্যালগরিদম যা রাবিন এবং কার্প প্রস্তাব করেছিলেন প্যাটার্নকে আরও দক্ষতার সাথে খুঁজে বের করার জন্য। নেইভ অ্যালগরিদম (Naive Algorithm)-এর মতো এটি ও উইন্ডোটি এক এক করে সরিয়ে প্যাটার্ন চেক করে, কিন্তু সব কেসে সব ক্যারেক্টার চেক না করে এটি হ্যাশ ভ্যালু (hash value) বের করে। হ্যাশ ভ্যালু ম্যাচ হলে তবেই এটি প্রতিটি ক্যারেক্টার চেক করতে থাকে। এইভাবে, প্রতি টেক্সট সাবসিকোয়েন্স (text subsequence)-এর জন্য শুধু একটা তুলনা হয় যা এটাকে প্যাটার্ন সার্চিং-এ আরও দক্ষ অ্যালগরিদম করে তোলে।
প্রিপ্রসেসিং টাইম (Preprocessing time): O(m)
রাবিন-কার্প অ্যালগরিদমের টাইম কমপ্লেক্সিটি O(m+n), কিন্তু ওৰস্ট কেস (worst case)-এ O(mn)।
আলগরিদম (Algorithm)
rabinkarp_algo(text, pattern, prime)
ইনপুট (Input) − মেইন টেক্সট (main text) এবং প্যাটার্ন (pattern)। হ্যাশ লোকেশন বের করার জন্য একটি প্রাইম নম্বর (prime number)।
আউটপুট (Output) − লোকেশনগুলো, যেখানে প্যাটার্নটি পাওয়া গেছে।
Start
pat_len := pattern Length
str_len := string Length
patHash := 0 and strHash := 0, h := 1
maxChar := ক্যারেক্টার সেটে টোটাল ক্যারেক্টার সংখ্যা
for index i of all character in the pattern, do
h := (h * maxChar) mod prime
for all character index i of pattern, 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
উদাহরণ (C প্রোগ্রাম)
#include <stdio.h>
#include <string.h>
int main() {
char txt[80], pat[80];
int q;
printf("Enter the container string:\n");
scanf("%s", txt);
printf("Enter the pattern to be searched:\n");
scanf("%s", pat);
int d = 256;
printf("Enter a prime number:\n");
scanf("%d", &q);
int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0; // pattern hash
int t = 0; // text hash
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
ব্যাখ্যা: রাবিন-কার্প অ্যালগরিদম রোলিং হ্যাশ (rolling hash) ব্যবহার করে। একটি প্রাইম নম্বর q মডুলো হিসেবে ব্যবহার করা হয়। হ্যাশ কলিশন (hash collision) হলে ক্যারেক্টার বাই ক্যারেক্টার ভেরিফাই করা হয়। এভারেজ কেসে O(n+m), ওৰস্ট কেসে O(nm)।
