Cho hai chuỗi A, B cùng độ dài. Mỗi dịch chuyển xoay B một ký tự. Tìm số dịch chuyển nhỏ nhất để tiền tố chung dài nhất. Ví dụ A="computerprogramming", B="programminglanguage" → dịch 8, tiền tố "programming".
Ghép B = B+B. Dùng thuật toán KMP tìm tiền tố dài nhất của A xuất hiện trong B, vị trí bắt đầu là số dịch chuyển.
Ví dụ
#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); }
Kết quả
Shift = 8 Prefix = programming