মনে করুন আমাদের দুটি স্ট্রিং A এবং B আছে। A এবং B-এর দৈর্ঘ্য একই। একটি শিফ্টে আমরা স্ট্রিং B-কে একটি এলিমেন্ট রোটেট করতে পারি। আমাদের কমন প্রিফিক্সের সর্বোচ্চ দৈর্ঘ্য পেতে A এবং B-র মধ্যকার ন্যূনতম শিফ্ট বের করতে হবে। তাই যদি A = "computerprogramming", এবং B = "programminglanguage" হয়, তবে ন্যূনতম শিফ্ট হল 8, এবং প্রিফিক্স হল "programming"।
মনে করুন আমরা স্ট্রিং B-কে B-এর শেষে যোগ করি, তাহলে B = B + B, তাহলে প্রতিটি শিফ্টের জন্য আলাদা করে প্রিফিক্স খুঁজে বের করতে হবে না। তাই আমাদের A-এর সবচেয়ে বড় প্রিফিক্স যেটি B-তে আছে সেটি বের করতে হবে, এবং 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
