C++에서 가장 긴 공통 접두사에 대한 최소 이동 찾기

두 개의 문자열 A와 B가 있다고 가정합니다. A와 B의 길이는 동일합니다. 단일 시프트에서 문자열 B를 한 요소로 회전할 수 있습니다. A와 B에서 최대 길이의 공통 접두사를 얻으려면 최소 요구 시프트를 찾아야 합니다. 따라서 A ="computerprogramming"이고 B ="programminglanguage"인 경우 최소 시프트는 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