বিবেচনা করুন আমাদের দুটি স্ট্রিং A এবং B আছে। A এবং B এর দৈর্ঘ্য একই। একটি সিঙ্গেল শিফটে আমরা স্ট্রিং B এক এলিমেন্ট ঘোরাতে পারি। A এবং B থেকে সর্বাধিক দৈর্ঘ্যের সাধারণ উপসর্গ পেতে আমাদের ন্যূনতম প্রয়োজনীয় শিফট খুঁজে বের করতে হবে। তাই যদি A =“কম্পিউটারপ্রোগ্রামিং”, এবং B =“প্রোগ্রামিং ল্যাঙ্গুয়েজ” তাহলে সর্বনিম্ন শিফট হল 8, এবং উপসর্গ হল “প্রোগ্রামিং”।
ধরুন আমরা B এর শেষে B স্ট্রিং যোগ করি, তাই B =B + B, তাহলে আলাদাভাবে প্রতিটি শিফটের উপসর্গ খুঁজে বের করার দরকার নেই। তাই আমাদের B-তে উপস্থিত A-এর দীর্ঘতম উপসর্গটি খুঁজে বের করতে হবে, এবং B-তে উপসর্গের শুরুর অবস্থান, প্রয়োজনীয় শিফটের প্রকৃত সংখ্যা দেবে।
উদাহরণ
#include<iostream>
using namespace std;
void KhuthMorrisPatt(int m, int n, string B, string A) {
int pos = 0, len = 0;
int p[m + 1];
int k = 0;
p[1] = 0;
for (int i = 2; i <= n; i++) {
while (k > 0 && A[k] != A[i - 1])
k = p[k];
if (A[k] == A[i - 1])
++k;
p[i] = k;
}
for (int j = 0, i = 0; i < m; i++) {
while (j > 0 && A[j] != B[i])
j = p[j];
if (A[j] == B[i])
j++;
if (j > len) {
len = j;
pos = i - j + 1;
}
}
cout << "Shift = " << pos << endl;
cout << "Prefix = " << A.substr(0, len);
}
int main() {
string A = "programminglanguage";
string B = "computerprogramming";
int n = A.size();
B = B + B;
KhuthMorrisPatt(2 * n, n, B, A);
} আউটপুট
Shift = 8 Prefix = programming
