এই সমস্যায়, আমাদের দুটি স্ট্রিং একটি পাঠ্য এবং একটি প্যাটার্ন দেওয়া হয়েছে। আমাদের কাজ হল প্যাটার্ন অনুসন্ধানের জন্য 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
