首页 > 代码库 > 最长公共子串+最长公共子序列
最长公共子串+最长公共子序列
两道题都可以用动态规划的方法做，只是状态转移方程不同。
最长公共子串（注意子串是连续的）
1、先建立一个二维数组array[str1.size()][str2.size()]（全部初始化为0），初始化第一行和第一列（元素相同处置1），然后进入状态方程
2、状态转移方程：
if(str1[i] == str2[i]) array[i][j]=array[i-1][j-1]+1; （左上方对角线的值加上1）
否则无操作。
3、最后寻找整个array中的最大值即可（因为可能有多个子串）
1 /* 2 本程序说明： 3 4 最长公共子串（注意空格，不要用cin，要用getline） 5 6 */ 7 #include <iostream> 8 #include <vector> 9 #include <string>10 using namespace std;11 12 int largestCommentSubString(std::string str1,std::string str2){13 if(0 == str1.length() || 0 == str2.length())14 return 0;15 16 std::vector<std::vector<int> > array(str1.size(),std::vector<int>(str2.size(),0));17 for(size_t i=0; i< str2.size(); ++i){18 if(str1[0] == str2[i])19 array[0][i]=1;20 }21 for(size_t i=0; i< str1.size(); ++i){22 if(str2[0] == str1[i])23 array[i][0]=1;24 }25 for(size_t i=1; i< str1.size(); ++i){26 for(size_t j=1; j< str2.size(); ++j){27 if(str1[i] == str2[j]){28 array[i][j]=array[i-1][j-1]+1;29 }30 }31 }32 int length=0;33 for(size_t i=0; i< array.size(); ++i){34 for(size_t j=0; j< array[0].size(); ++j){35 if(array[i][j]>length){36 length=array[i][j];37 }38 }39 }40 return length;41 }42 43 int main(){44 std::string str1,str2;45 while(getline(cin,str1),getline(cin,str2)){ 46 cout<<largestCommentSubString(str1,str2)<<endl;47 }48 return 0;49 }
最长公共子序列（注意子序列可以不连续）
1、先建立一个二维数组array[str1.size()+1][str2.size()+1]（全部初始化为0），然后进入状态方程
2、状态转移方程：
if(str1[i] == str2[i]) array[i][j]=array[i-1][j-1]+1; （左上方对角线的值加上1）
if(str1[i] != str2[i]) array[i][j]=max(array[i-1][j],array[i][j-1]); （左边和上边的最大值）
3、最后返回整个array中的最大值即可（即array右下角元素的值）
1 /* 2 本程序说明： 3 4 最长公共子序列 5 6 */ 7 #include <iostream> 8 #include <vector> 9 #include <string>10 using namespace std;11 12 int findLCS(string str1,string str2) {13 // write code here14 if(0 == str1.size() || 0 == str2.size())15 return 0;16 vector<vector<int> > array(str1.size()+1,vector<int>(str2.size()+1,0));17 for(size_t i=1; i<= str1.size(); ++i){//注意：是小于等于18 for(size_t j=1; j<= str2.size(); ++j){//注意：是小于等于19 if(str1[i-1] == str2[j-1]){//前面填充了一行一列，因此判断i-1和j-120 array[i][j]=array[i-1][j-1]+1;21 }22 else23 array[i][j]=max(array[i-1][j],array[i][j-1]);24 }25 }26 return array[str1.size()][str2.size()];27 }28 29 int main(){30 string str1,str2;31 while(getline(cin,str1),getline(cin,str2)){32 cout<<findLCS(str1,str2)<<endl;33 }34 return 0;35 }
如果还要进一步打印出其中一个公共子序列的话，需要用到回溯法。我们在动态规划时需要记录元素的状态，一步步回溯回去即可。
1 /* 2 本程序说明： 3 4 最长公共子序列（加上了其中一个子序列的打印功能，回溯法） 5 6 */ 7 #include <iostream> 8 #include <vector> 9 #include <string>10 using namespace std;11 12 //打印（回溯法）13 void printLCS(const string& str1,const string& str2,const vector<vector<string> >& flag,int i,int j,string& str)14 {15 if(0==i||0==j)16 return;17 if("left_up"==flag[i][j])18 {19 str.insert(str.begin(),str1[i-1]);//把要打印的公共字符逆序存在str中(因为回溯法从后向前，所以需要逆序)20 printLCS(str1,str2,flag,i-1,j-1,str);21 }22 else if("left"==flag[i][j])23 printLCS(str1,str2,flag,i-1,j,str);24 else if("up"==flag[i][j])25 printLCS(str1,str2,flag,i,j-1,str);26 }27 28 int findLCS(const string& str1,const string& str2) {29 // write code here30 if(0 == str1.size() || 0 == str2.size())31 return 0;32 vector<vector<string> > flag(str1.size()+1,vector<string>(str2.size()+1,""));//记录状态33 vector<vector<int> > array(str1.size()+1,vector<int>(str2.size()+1,0));34 for(size_t i=1; i <= str1.size(); ++i){//注意：是小于等于35 for(size_t j=1; j<= str2.size(); ++j){//注意：是小于等于36 if(str1[i-1] == str2[j-1]){//前面填充了一行一列，因此判断i-1和j-137 array[i][j] = array[i-1][j-1]+1;38 flag[i][j] = "left_up";39 }40 else41 {42 if(array[i-1][j] > array[i][j-1])43 {44 array[i][j] = array[i-1][j];45 flag[i][j] = "left";46 }47 else/*(array[i-1][j] < array[i][j-1])*/48 {49 array[i][j] = array[i][j-1];50 flag[i][j] = "up";51 }52 }53 }54 }55 56 string str="";57 printLCS(str1,str2,flag,str1.size(),str2.size(),str);58 cout<<"公共子序列： "<<str<<endl;59 return array[str1.size()][str2.size()];60 }61 62 int main(){63 std::string str1,str2;64 while(getline(cin,str1),getline(cin,str2)){65 cout<<findLCS(str1,str2)<<endl;66 }67 return 0;68 }
参考文章：http://www.cnblogs.com/huangxincheng/archive/2012/11/11/2764625.html
最长公共子串+最长公共子序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。