输出两个字符串的最长公共子串和最长公共子序列（不仅仅是求长度）。

求解两个字符串的最长公共子串和最长公共子序列在方法上很接近，都是动态规划。只不过在递推方程上有一些不一样。

 

输出两个字符串的最长公共子串

#include 
     
      using namespace std; string LCS(const string& str1, const string& str2){    if(str1.empty() || str2.empty()){        return "";    }         int indexMax=0, maxn=0;    vector
      
       
         > L(str1.size(), vector
        
         (str2.size(),0) );   //全部初始化为0    //L[i][j]代表 str1[0~i-1]和str2[0~j-1] 的最长公共子串的长度       for(int i=0; i
         
           maxn){                maxn=L[i][j];   //记录下最长公共子串的长度                indexMax=i;     //记录下出现“最长公共子串”时的末尾字符的位置            }        }    }    return str1.substr(indexMax+1-maxn, maxn);      //字符串截取的长度有(end-start+1) = maxn, 那么start = end+1-maxn     // indexMax - (indexMax+1-maxn) + 1 = maxn, maxn即为所截取的字符串的长度。}  int main(){    string str1, str2;    string cur;    while( getline(cin,cur) ){        if(str1.empty()) str1 = cur;        else if(str2.empty()) str2 = cur;                 if(!str1.empty() && !str2.empty() ){             cout<< LCS(str1, str2) <
         
        
       
      
     

　　

 

输出两个字符串的最长公共子序列。公共子序列和公共子串的区别在于，序列不要求连续，子串要求是其在原串中是连续的。

参考链接：

 

#include 
     
      using namespace std;//输出最长公共子串（LCS）//二维数组veca记录的是两个字符串Xi和Yj的LCS长度int LCS_length(const string &str1, const string &str2, 	            vector
      
       
         > &veca, vector
        
         
           > &vecb) {	int i, j; 	if (str1 == "" || str2 == "")		return 0; 	for (i = 0; i <= str1.length(); i++) {		veca[i][0] = 0;	}	for (j = 0; j <= str2.length(); j++) {		veca[0][j] = 0;	}	for (i = 1; i <= str1.length(); i++) {		for (j = 1; j <= str2.length(); j++) {			//如果Xi-1 == Yj-1，那么最长子序列为veca[i - 1][j - 1] + 1			//此时将vecb[i][j] = 1表明str1[i-1]是子问题LCS的一个元素			if (str1[i - 1] == str2[j - 1]) {				veca[i][j] = veca[i - 1][j - 1] + 1;				vecb[i][j] = 1;			}			else {				if (veca[i - 1][j] >= veca[i][j - 1]) {					veca[i][j] = veca[i - 1][j];					vecb[i][j] = 2; //记录方向,如果为2,那就往左走				}				else {					veca[i][j] = veca[i][j-1];					vecb[i][j] = 3; //记录方向,如果为3,那就往上走 				}			}		}	}	return veca[str1.length()][str2.length()];} //该函数用于输出一个LCS的序列//这里输出的顺序是先向上寻找，再向左寻找void PrintOneLCS(vector
          
           
             > &vecb, string &str1, string &str2, int i, int j) { if (i == 0 || j == 0) return; if (vecb[i][j] == 1) { PrintOneLCS(vecb, str1,str2, i - 1, j - 1); cout << str1[i - 1]; //这里输出str1[i-1]和str2[j-1]都是一样的 // cout << str2[j - 1]; } else if (vecb[i][j] == 2) PrintOneLCS(vecb, str1, str2, i -1, j); else PrintOneLCS(vecb, str1, str2, i, j - 1);}int main() { string input; getline(cin, input); stringstream ss(input); string str1, str2; ss >> str1; ss >> str2; //将veca初始化为一个二维数组,其行列值分别为str1和str2的长度加1 //二维数组veca记录的是两个字符串Xi和Yj的LCS长度 //二维数组vecb[i][j]记录veca[i][j]时所选择的子问题的最优解 vector
            
             
               > veca(str1.length() + 1, vector
              
               (str2.length() + 1)); vector
               
                
                  > vecb(str1.length() + 1, vector
                 
                  (str2.length() + 1)); cout << LCS_length(str1, str2, veca, vecb) << endl; PrintOneLCS(vecb, str1, str2, str1.length(), str2.length()); return 0;}