এই সমস্যাতে, আমাদের দুটি স্ট্রিং দেওয়া আছে: একটি টেক্সট এবং একটি প্যাটার্ন। আমাদের কাজ হল KMP অ্যালগরিদম ব্যবহার করে প্যাটার্ন সার্চের প্রোগ্রাম তৈরি করা, যা টেক্সট স্ট্রিং-এ প্যাটার্নের সকল আওয়ারেন্স খুঁজে বের করবে।
এখানে, আমাদের টেক্সট-এ প্যাটার্নের সকল আওয়ারেন্স খুঁজে বের করতে হবে।
সমস্যা বোঝার জন্য একটি উদাহরণ নিই,
ইনপুট
text = "xyztrwqxyzfg" pattern = "xyz"
আউটপুট
Found at index 0 Found at index 7
এখানে, আমরা KMP (Knuth Morris Pratt) প্যাটার্ন সার্চিং অ্যালগরিদম ব্যবহার করে সমস্যার সমাধান আলোচনা করব, যা প্যাটার্নের একটি প্রিপ্রসেসিং স্ট্রিং ব্যবহার করে যা টেক্সট-এ ম্যাচিংয়ের জন্য ব্যবহৃত হয়। এবং এটি بتلكে সাহায্য করে যেখানে ম্যাচিং ক্যারেক্টারها স্ট্রিং-এর এমন ক্যারেক্টার দ্বারা অনুসরণ করা হয় যা প্যাটার্নের সাথে মেলে না।
আমরা প্যাটার্নকে প্রিপ্রসেস করব একটি অ্যারে তৈরি করার জন্য যাতে প্যাটার্ন থেকে প্রপার প্রিফিক্স এবং সাফিক্স থাকে যা মিসম্যাচ প্যাটার্ন খুঁজে বের করতে সাহায্য করবে।
KMP অ্যালগরিদম প্যাটার্ন সার্চিংয়ের প্রোগ্রাম
// KMP অ্যালগরিদম প্যাটার্ন সার্চিংয়ের C প্রোগ্রাম
উদাহরণ
#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
