动态规划??最长公共子序列问题(LCS)

发布于:2021-10-31 03:02:08

最长公共子序列问题
也就是如在两个不同的字符串中找出最长的公共子序列

例:


字符串x = "ABCBDAB"
字符串y = "BDCABA"


可以看出他们的公共子序列是 BCBA,但是对于较长的字符串,肉眼很难去判断,如果用枚举,那么其算法复杂度为O(

2m
)就要寻找一种算法复杂度较低的算法 ,就是先比较字符串x和y各个字符已经有几个相同的情况,存在c中,空间复杂度和时间复杂度都为O(m*n)。b中存的是走的路径,约定,起点为b的右下角,如果b中存的为2,则为向上走;如果为1,则为向斜左上方走;如果为0,向左走。



程序伪代码:
    计算c和b
    统计返回公共子串,这里我将它修改了一下,伪代码是找到就输出 ,我修改为了整个找完后再返回
    程度实现

实现的具体代码

#include
#include

using namespace std;

void lcs_length(string x, string y, int **c, int**b){
int lenx = x.length();
int leny = y.length();

//if b[i][j] means the orientation of c[i][j]
// b[i][j] = 0 ---> move left
// b[i][j] = 1 ---> move up and left
// b[i][j] = 2 ---> move up
for (int i = 1; i <= lenx; ++i){
for (int j = 1; j <= leny; ++j){
//字符串索引是从0开始
if (x[i-1] == y[j-1]){
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 1;
}
else if (c[i - 1][j] >= c[i][j - 1]){
c[i][j] = c[i - 1][j];
b[i][j] = 2;
}
else{
c[i][j] = c[i][j - 1];
//b[i][j] = 0;
}
}
}
}

string print_lcs(int **b, string x, int i, int j){
string res;
if (i == 0 || j == 0){
return "";
}
if (b[i][j] == 1){//代表此时两个是相同的,但是在字符串x中,索引要小1
res += print_lcs(b, x, i - 1, j - 1);
res += x[i - 1];
}
else if (b[i][j] == 2){
res += print_lcs(b, x, i - 1, j);
}
else{
res += print_lcs(b, x, i, j - 1);
}
return res;
}

int main(){
string x;
string y;
getline(cin,x);
getline(cin,y);
string res;
int lenx = x.length();
int leny = y.length();

//init c and b to 0
int **c = new int*[lenx + 1];
for (int i = 0; i <= lenx; ++i){
c[i] = new int[leny + 1]();
}
int **b = new int*[lenx + 1];
for (int i = 0; i <= lenx; ++i){
b[i] = new int[leny + 1]();
}

lcs_length(x, y, c, b);
res = print_lcs(b, x, lenx, leny);
cout << res << endl;

//释放new的空间
for (int i = 0; i <= lenx; ++i){
delete[]c[i];
}
delete[]c;
for (int i = 0; i <= leny; ++i){
delete[]b[i];
}

return 0;
}

测试用例1:


测试用例2:

相关推荐

最新更新

猜你喜欢