在C ++中找到最长的公共前缀的最小移位

考虑我们有两个字符串A和B。A和B的长度相同。只需一次移位，我们就可以将字符串B旋转一个元素。我们必须找到最小所需的偏移量才能从A和B获得最大长度的通用前缀。因此，如果A =“计算机编程”，而B =“编程语言”，则最小偏移为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