子序列与子串不同，子串一定要连续，子序列可以不连续！ 对于给定的两个序列 X{x1, x2, x3, … },Y{y1, y2, y3, …};求X与Y的最长公共子序列，可采用动态规划的方法。 1.当x1 = y1时，则此时已找到一个相同的值，故接下来只需求{x2, x3, x4, …}和{y2, y3, y4, …}的LCS。 2.当x1 != y1时，则此时X和Y的LCS是下面两个LCS的最大值： {x2, x3, x4, …}和{y1, y2, y3, y4, …}的LCS， 或者{x1, x2, x3, x4, …}和{y2, y3, y4, …}的LCS。 由上面可以看出这是一个递归问题。 求解： 第一步：先计算最长公共子序列的长度。
第二步：根据长度，然后通过回溯求出最长公共子序列。
即：
代码如下：
#include <iostream> #include <cstring> using namespace std; char x[100]; char y[100]; int c[100][100];//二维矩阵存储公共子序列长度 int max(int a,int b); char *LCS(char x[],char y[]);//求最长公共子序列 int main(){ int x1,y1;//两个字符串的长度 cout<<"请分别输入第一、二个字符串长度"<<endl; cin>>x1>>y1; cout<<"输入第一个字符串"<<endl; for(int i=0;i<x1;i++){ cin>>x[i]; } cout<<"输入第二个字符串"<<endl; for(int i=0;i<y1;i++){ cin>>y[i]; } char *s=LCS(x,y); cout<<"最长公共子序列为："<<s<<endl; cout<<"长度为："<<strlen(s)<<endl; return 0; } char *LCS(char x[],char y[]){ int x1=strlen(x); int y1=strlen(y); for(int i=0;i<x1;i++) { c[i][0]=0; } for(int i=0;i<y1;i++){ c[0][i]=0; } for(int i=0;i<x1;i++){//填充矩阵 for(int j=0;j<y1;j++){ if(x[i]==y[j]){//相等的情况 c[i+1][j+1]=c[i][j]+1; } else{//不等，选大的 c[i+1][j+1]=max(c[i][j+1],c[i+1][j]); } } } int len=c[x1][y1]; int count=len; char * lcs=new char[len+1]; while(x1>0&&y1>0){//回溯法求解子序列 if(c[x1][y1]==c[x1-1][y1-1]+1&&x[x1-1]==y[y1-1]){ //判断序列中是否有子序列的元素 lcs[--count]=x[x1-1]; x1--; } else if(c[x1][y1]==c[x1][y1-1]){ y1--; } else{ x1--; } } return lcs; } int max(int a,int b){ if(a>=b){ return a; } else return b; }