数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时装学
法律学在 C++ 中查找最长公共前缀的最小移动次数
假设我们有两个字符串 A 和 B。A 和 B 的长度相同。在一个移动中，我们可以将字符串 B 旋转一个元素。我们必须找到从 A 和 B 获得最大长度公共前缀所需的最小移动次数。因此，如果 A =“computerprogramming”，而 B =“programminglanguage”，则最小移动次数为 8，前缀为“programming”。
假设我们在 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
更新于： 18-12-2019
393 次浏览
广告