在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