c++算法和数据结构之《LCS》

数据结构之《LCS》"/>

c++算法和数据结构之《LCS》

文章目录

• 动态规划求解最长公共子序列的结构
• • 一：递归算法
  • 二：非递归算法

动态规划求解最长公共子序列的结构

分析规律：
设X=<x1,x2,x3,x4…,xm>，Y=<y1,y2,y3,y4…,yn>为两个序列，Z=<z1,z2,z3,z4…,zk>是他们的任意公共子序列

经过分析，我们可以知道：

1、如果xm = yn，则zk = xm = yn 且 Zk-1是Xm-1和Yn-1的一个LCS
2、如果xm != yn 且 zk != xm，则Z是Xm-1和Y的一个LCS
3、如果xm != yn 且 zk != yn，则Z是X和Yn-1的一个LCS

所以如果用一个二维数组c表示字符串X和Y中对应的前i，前j个字符的LCS的长度话，可以得到以下公式：

思路：
如上述我们已经总结出了计算最长公共子序的公式，但为了降低程序的时间复杂度，也就是为了减少计算max（c[j,j-1],c[i-1,j]）的重复计算次数，我们用一个动态二维数组来存放先前已经计算过的内容，防止后续重复运算而导致的时间复杂度升高。用另外一个动态二维数组来存放公共子序的方向坐标，为了能够打印出公共子序的具体值。

一：递归算法

#include<iostream>
#include<vector>
#include<limits.h>
#include<string>
#include<deque>
using namespace std;int Recursive_LCSlength(char X[], char Y[], int i, int j,vector<vector<int >>& c, vector<vector<int>>& s)
{if (i == 0 || j == 0)return 0;else if (c[i][j] > 0)return c[i][j];else if (X[i] == Y[j]){c[i][j] = Recursive_LCSlength(X, Y, i - 1, j - 1, c, s) + 1;s[i][j] = 1;}else{int maxlen1 = Recursive_LCSlength(X, Y, i - 1, j, c, s);int maxlen2 = Recursive_LCSlength(X, Y, i, j - 1, c, s);if (maxlen1 > maxlen2){c[i][j] = maxlen1;s[i][j] = 2;}else{c[i][j] = maxlen2;s[i][j] = 3;}}return c[i][j];
}void Print_Vector(vector<vector<int >>& c, int m, int n)
{for (int i = 0;i <= m;i++){for (int j = 0; j <= n;j++){cout << c[i][j] << " ";}cout << endl;}cout << endl;
}void Print_String(char X[], vector<vector<int>>& s, int m, int n)
{if (m == 0 || n == 0)return;if (s[m][n] == 1){Print_String(X, s, m - 1, n - 1);cout << X[m] << " ";}else if (s[m][n] == 2){Print_String(X, s, m - 1, n);}else{Print_String(X, s, m, n - 1);}
}int main()
{const int m = 7;const int n = 6;char X[m + 2] = { "#ABCEFAB" };char Y[n + 2] = { "#ACFBEB" };vector<vector<int>> c, s;   //c来存放已经计算过的步骤，s来存放公共子序的方向坐标c.resize(m + 1);s.resize(m + 1);for (int i = 0;i <= m;i++){c[i].resize(n + 1);s[i].resize(n + 1);}int maxlen = LCSlength(X, Y, m, n, c, s);Print_Vector(c, m, n);Print_Vector(s, m, n);cout << maxlen << endl;Print_String(X, s, m, n);return 0;
}

二：非递归算法

思路：
循环比较两个值的大小是否相等，如果相等，则该坐标值等于左上角离该值最近的一个坐标值加1，如果不相等，则该坐标值等于该坐标上边或左边最大的那一个坐标值。

int LCSlength(char X[], char Y[], int m, int n,vector<vector<int >>& c, vector<vector<int>>& s)
{for (int i = 0;i <= m;++i){c[i][0] = 0;s[i][0] = 0;}for (int j = 0;j <= n;++j){c[0][j] = 0;s[0][j] = 0;} for (int i = 1;i <= m;++i)     //X{for (int j = 1;j <= n;++j)  //Y{if (X[i] == Y[j]){c[i][j] = c[i - 1][j - 1] + 1;s[i][j] = 1;}else if(c[i-1][j]> c[i][j-1]){c[i][j] = c[i - 1][j];s[i][j] = 2;}else{c[i][j] = c[i ][j - 1];s[i][j] = 3;}}}return c[m][n];
}