พิจารณาว่าเรามีสาย A และ B สองสาย ความยาวของ A และ B เท่ากัน ในกะเดียวเราสามารถหมุนสตริง B หนึ่งองค์ประกอบ เราต้องหากะขั้นต่ำที่จำเป็นเพื่อให้ได้คำนำหน้าร่วมกันของความยาวสูงสุดจาก A และ B ดังนั้นถ้า A =“computerprogramming” และ B =“programminglanguage” ดังนั้นกะขั้นต่ำคือ 8 และ prefix คือ “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
