資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚學
法律學以字典序列印 C++ 中所有最長公共子序列
在這個問題中，我們給出了兩個字串 str1 和 str2。我們的任務是建立一個程式來以字典序列印所有最長公共子序列。
讓我們透過一個示例來理解問題，
輸入：str1 = “gfare” , str2 = “rfare”
輸出：fare
解決方案思路
在這個問題中，我們將使用動態規劃找到所有可能的公共子序列，並將它們儲存在一個二維矩陣中。在此之後，我們將透過在 LCS 中搜索從 a 到 z 的字元來列印排序後的輸出。
為了說明我們解決方案的工作原理，這裡有一個程式，
示例
#include<iostream>
#include<cstring>
#define MAX 100
using namespace std;
int LCSLength = 0;
int DP[MAX][MAX];
int calcLCSLenght(string str1, string str2, int l1, int l2, int i, int j) {
int &lcsLen = DP[i][j];
if (i==l1 || j==l2)
return lcsLen = 0;
if (lcsLen != -1)
return lcsLen;
lcsLen = 0;
if (str1[i] == str2[j])
lcsLen = 1 + calcLCSLenght(str1, str2, l1, l2, i+1, j+1);
else
lcsLen = max(calcLCSLenght(str1, str2, l1, l2, i+1, j), calcLCSLenght(str1, str2, l1, l2, i, j+1));
return lcsLen;
}
void printAllLCS(string str1, string str2, int l1, int l2, char data[], int index1, int index2, int currentLCSlength) {
if (currentLCSlength == LCSLength) {
data[currentLCSlength] = '\0';
puts(data);
return;
}
if (index1==l1 || index2==l2)
return;
for (char ch='a'; ch<='z'; ch++) {
bool done = false;
for (int i=index1; i<l1; i++) {
if (ch==str1[i]) {
for (int j=index2; j<l2; j++) {
if (ch==str2[j] && calcLCSLenght(str1, str2, l1, l2, i, j) == LCSLength-currentLCSlength) {
data[currentLCSlength] = ch;
printAllLCS(str1, str2, l1, l2, data, i+1, j+1, currentLCSlength+1);
done = true;
break;
}
}
}
if (done)
break;
}
}
}
int main() {
string str1 = "xysxysx", str2 = "xsyxsyx";
int l1 = str1.length(), l2 = str2.length();
memset(DP, -1, sizeof(DP));
LCSLength = calcLCSLenght(str1, str2, l1, l2, 0, 0);
char data[MAX];
cout<<"All longest common sub-sequences in lexicographical order are\n";
printAllLCS(str1, str2, l1, l2, data, 0, 0, 0);
return 0;
}輸出
All longest common sub-sequences in lexicographical order are xsxsx xsxyx xsysx xysyx xyxsx xyxyx
更新於：2021 年 1 月 27 日
746 次瀏覽
廣告