資料結構
網路
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 次瀏覽
廣告