Tìm dịch chuyển tối thiểu cho tiền tố chung dài nhất trong C ++

Coi chúng ta có hai chuỗi A và B. Độ dài của A và B là như nhau. Trong một lần thay đổi, chúng ta có thể xoay chuỗi B một phần tử. Chúng ta phải tìm sự dịch chuyển bắt buộc tối thiểu để nhận được tiền tố chung có độ dài tối đa từ A và B. Vì vậy, nếu A =“computerprogramming” và B =“Progralanguage” Vậy thì sự dịch chuyển tối thiểu là 8 và tiền tố là “Lập trình”.

Giả sử chúng ta thêm chuỗi B vào cuối B, do đó B =B + B, khi đó không cần tìm tiền tố của mỗi ca riêng biệt. Vì vậy, chúng ta phải tìm tiền tố dài nhất của A có trong B và vị trí bắt đầu của tiền tố trong B, sẽ cho số lần dịch chuyển thực tế cần thiết.

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);
}

Đầu ra

Shift = 8
Prefix = programming