LSC最长公共子序列c++实现

邓俊辉版数据结构，动态规划求解最长公共子序列学习总结。
第一种方法是通过递归实现。思路如下，两字符串长度长度分别为 a,b，比较他们的末位字符，这里是有三种情况

1. 若有一方长度为零，则返回“”，这是递归方程的递归基。
2. 若两字符串的末位字符相同，去掉末尾字符，返回规模递减的问题f(a-1,b-1)。这里是“减而治之”策略。
3. 若两字符串末位字符不同，则有两种情况通过比较(a-1,b) 和(a,b-1)长度的字符串的最长公共子序列的长度，像长度较大的方向继续进行递归，返回f(a-1,b)或f(a,b-1),这里用的是“分而治之”策略。

实现代码如下

#include 
using namespace std;
string substring = ""; 
string lcs(string s1,string s2);
int main(){string s1, s2;cout << "please enter the first string\n";cin >> s1;cout << "please enter the second string\n";cin >> s2;cout<<"the longest conmmon subsequence is "<<lcs(s1, s2);
}
string lcs(string s1,string s2){   int a,b;a = s1.length()-1;b = s2.length()-1;if(a==-1||b==-1){//substring += "";//reverse(substring.begin(),substring.end());return "";}else if(s1[a]==s2[b]){//substring += s1[a];char m = s1[a];s1 = s1.substr(0, a);s2 = s2.substr(0, b);return lcs(s1,s2)+m;}else{string s11 = s1.substr(0, a);string s22 = s2.substr(0, b);int l1 = lcs(s11, s2).length();int l2 = lcs(s1, s22).length();if(l1>l2){s1 = s11;return lcs(s1,s2);}else{s2 = s22;return lcs(s1,s2);}}
}

这种递归的方法由于多次重复计算，时间复杂度在最坏情况下达到O(2^n).

第二种方法是用迭代，通过动态规划用表来存储较短的字符串的公共子序列长度，就避免的了大量重复计算，方法是上面递归方法的逆向执行，比如1313和
431254的最长公共子序列，列表
0 0 0 0 0 0 0
0 0 0 1 1 1 1
0 0 1 1 1 1 1
0 0 1 2 2 2 2
0 0 1 2 2 2 2
通过循环遍历长宽为a+1,b+1的列表，第一行和第一列初始化为0，相同就填入左上加一，不同就填入左边或上面格子中较大的那个数，填满表格，表格的最右下角即为所求最长公共子序列的长度。
下面是一开始写的，可以得到正确长度但输出的最长公共子序列有误。

#include 
using namespace std;
string substring = "";
int maxelement = 0;
int max(int *p, int a, int b);
string lcs(string s1,string s2);
int main(){string s1, s2;cout << "please enter the first string\n";cin >> s1;cout << "please enter the second string\n";cin >> s2;string s = lcs(s1, s2);cout<<"the longest conmmon subsequence is "<<s;
}
string lcs(string s1,string s2){int a = s1.length();int b = s2.length();int list[a+1][b + 1];for (int m = 0; m < a + 1;m++){for (int n = 0; n < b + 1;n++){list[m][n] = 0;}}for (int i = 1; i < a + 1; i++){for (int j = 1; j < b + 1; j++){if (s1[i-1] == s2[j-1]){list[i][j] = list[i - 1][j - 1] + 1;if (list[i][j] >= max(list[0],a+1,b+1)){//cout << "ii" << i << "jj" << j;substring += s1[i - 1];}}else{list[i][j] = (list[i - 1][j] > list[i][j - 1]) ? list[i - 1][j] : list[i][j - 1];}}}for (int m = 0; m < a + 1;m++){for (int n = 0; n < b + 1;n++){cout<<" "<<list[m][n];}cout << "\n";}return substring;
}
int max(int *p,int a,int b){int max = 0;for (int i = 0; i < a;i++){for (int j = 0; j<b;j++){if(*( p+i*b+j)>max){max = *(p + i * b + j);}}}if(max > maxelement){maxelement = max;}else if(max==maxelement){max = max + 1;}return max;
}

经过手动测试，以上程序不能正确输出最长公共子序列的原因在于它通过找到记录列表中令每个最大值第一次出现的那个字符，并加入substring。但像这样判断是不完善的，第一次匹配到的元素是不会随着更大更长的公共子序列的出现而替换的。因此通过一个标志数组来记录搜索进行的方向，然后再由得到最长公共子序列的那一条路径求得这两个字符串的最长公共子序列。

实现代码

#include 
using namespace std;
string substring = "";
int symbol[100][100];
void lcs(string s1,string s2);
string show(int i, int j, string x);
int main(){string s1, s2;cout << "please enter the first string\n";cin >> s1;cout << "please enter the second string\n";cin >> s2;lcs(s1, s2);show(s1.length(), s2.length(), s1);cout<<"the longest conmmon subsequence is "<<substring;
}
void lcs(string s1,string s2){int a = s1.length();int b = s2.length();int list[a+1][b + 1];for (int m = 0; m < a + 1;m++){for (int n = 0; n < b + 1;n++){list[m][n] = 0;}}for (int i = 1; i < a + 1; i++){for (int j = 1; j < b + 1; j++){if (s1[i-1] == s2[j-1]){list[i][j] = list[i - 1][j - 1] + 1;symbol[i][j] = 0;}else if(list[i - 1][j] > list[i][j - 1]){list[i][j] = list[i - 1][j];symbol[i][j] = 1;}else{list[i][j] = list[i][j - 1];symbol[i][j] = 2;}                }}for (int m = 0; m < a + 1;m++){for (int n = 0; n < b + 1;n++){cout<<" "<<symbol[m][n];}cout << "\n";}
}
string show(int i,int j,string x)
{if(i==0||j==0)return substring;if(symbol[i][j]==0){show(i-1,j-1,x);substring+=x[i-1];return substring;}else if(symbol[i][j]==1){show(i-1,j,x);return substring;}else{show(i,j-1,x);return substring;}
}

此方法的时间复杂度是o(m+n+m * n),包括求字符的m + n和求字符串长度的m * n。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！