最长公共子序列
一、最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（LongestCommon Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
例如：X（A，B，C，B，D，A，B）
Y(B，D，C，A，B，A)
那么最长公共子序列就是：B，C，B，A
二、算法设计：
方法一、穷举法
解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。X和Y的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列{1, 2, …, m}的一个子序列，因此，X共有2m个不同子序列（Y亦如此，如为2^n），从而穷举搜索法需要指数时间（2^m
* 2^n）。
方法二、用动态规划方法解决
最长公共子序列的结构：
设X = { x1 ,... , xm },Y = { y1 , ... , yn }及它们的最长子序列Z= { z1 , ... , zk }则：
1、若 xm = yn ， 则 zk = xm = yn，且Z[k-1] 是 X[m-1] 和 Y[n-1] 的最长公共子序列
2、若 xm != yn ，且 zk != xm, 则 Z 是 X[m-1] 和 Y 的最长公共子序列
3、若 xm != yn , 且 zk != yn, 则 Z 是 Y[n-1] 和 X 的最长公共子序列
子问题的递归结构：
1、当 i = 0 , j = 0 时 , c[i][j] = 0
2、当 i , j > 0 ; x[i-1] = y[j-1] 时 , c[i][j] = c[i-1][j-1] + 1
3、当 i , j > 0 ; xi[i-1]!= y[j-1] 时 , c[i][j] = max { c[i][j-1] , c[i-1][j] }
算法:
打印(回溯法):
由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m + n)次就会遇到i = 0或j = 0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为Θ(m + n)。
算法详细示例图:
代码一:
/*
Right:greenday
*/
#include<stdio.h>
#include<string.h>
//打印最长序列
void Display(int bin[][], char x[], int i, int j) {
if(i == 0 || j == 0)
return;
if(b[i][j] == 1)
{
Display(bin, x, i-1, j-1);
System.out.print(x[i] + " ");
}
else if(bin[i][j] == 0)
{
Display(bin, x, i-1, j);
}
else if(bin[i][j] == -1)
{
Display(bin, x, i, j-1);
}
}
int main(){
int num;
scanf("%d",&num);
while(num--){
char tring1[1001];
char tring2[1001];
int slenth[1001][1001];
int lujing[1001][1001];
scanf("%s",tring1);
scanf("%s",tring2);
//gets(tring1);
//gets(tring2);
int len1=strlen(tring1);//LCS
int len2=strlen(tring2);
//初始数组点值为1，至少长度为1
for(int i=0;i<=len1;i++)
slenth[i][0]=0;
for(int j=0;j<=len2;j++)
slenth[0][j]=0;
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
//判断字母的大小
if(tring1[i-1]==tring2[j-1]){
//动态规划
slenth[i][j]=slenth[i-1][j-1]+1;
lujing[i][j]=1;
}
else if(slenth[i][j-1]>slenth[i-1][j]){
slenth[i][j]=slenth[i][j-1];
lujing[i][j]=-1;
}
else{
slenth[i][j]=slenth[i-1][j];
lujing[i][j]=0;
}
}
}
printf("%d\n",slenth[len1][len2]);//LCS
}
return 0;
}
代码二:
#include "stdafx.h"
#include "string.h"
#include <iostream>
using namespace std;
// directions of LCS generation
enum decreaseDir {kInit = 0, kLeft, kUp, kLeftUp};
void LCS_Print(int **LCS_direction, char* pStr1, char* pStr2, size_t row, size_t col);
// Get the length of two strings' LCSs, and print one of the LCSs
// Input: pStr1 - the first string
// pStr2 - the second string
// Output: the length of two strings' LCSs
int LCS(char* pStr1, char* pStr2)
{
if(!pStr1 || !pStr2)
return 0;
size_t length1 = strlen(pStr1);
size_t length2 = strlen(pStr2);
if(!length1 || !length2)
return 0;
size_t i, j;
// initiate the length matrix
int **LCS_length;
LCS_length = (int**)(new int[length1]);
for(i = 0; i < length1; ++ i)
LCS_length[i] = (int*)new int[length2];
for(i = 0; i < length1; ++ i)
for(j = 0; j < length2; ++ j)
LCS_length[i][j] = 0;
// initiate the direction matrix
int **LCS_direction;
LCS_direction = (int**)(new int[length1]);
for( i = 0; i < length1; ++ i)
LCS_direction[i] = (int*)new int[length2];
for(i = 0; i < length1; ++ i)
for(j = 0; j < length2; ++ j)
LCS_direction[i][j] = kInit;
for(i = 0; i < length1; ++ i)
{
for(j = 0; j < length2; ++ j)
{
//之前此处的代码有问题，现在订正如下：
if(i == 0 || j == 0)
{
if(pStr1[i] == pStr2[j])
{
LCS_length[i][j] = 1;
LCS_direction[i][j] = kLeftUp;
}
else
{
if(i > 0)
{
LCS_length[i][j] = LCS_length[i - 1][j];
LCS_direction[i][j] = kUp;
}
if(j > 0)
{
LCS_length[i][j] = LCS_length[i][j - 1];
LCS_direction[i][j] = kLeft;
}
}
}
// a char of LCS is found,
// it comes from the left up entry in the direction matrix
else if(pStr1[i] == pStr2[j])
{
LCS_length[i][j] = LCS_length[i - 1][j - 1] + 1;
LCS_direction[i][j] = kLeftUp;
}
// it comes from the up entry in the direction matrix
else if(LCS_length[i - 1][j] > LCS_length[i][j - 1])
{
LCS_length[i][j] = LCS_length[i - 1][j];
LCS_direction[i][j] = kUp;
}
// it comes from the left entry in the direction matrix
else
{
LCS_length[i][j] = LCS_length[i][j - 1];
LCS_direction[i][j] = kLeft;
}
}
}
LCS_Print(LCS_direction, pStr1, pStr2, length1 - 1, length2 - 1); //调用下面的LCS_Pring 打印出所求子串。
return LCS_length[length1 - 1][length2 - 1]; //返回长度。
}
// Print a LCS for two strings
// Input: LCS_direction - a 2d matrix which records the direction of
// LCS generation
// pStr1 - the first string
// pStr2 - the second string
// row - the row index in the matrix LCS_direction
// col - the column index in the matrix LCS_direction
void LCS_Print(int **LCS_direction, char* pStr1, char* pStr2, size_t row, size_t col)
{
if(pStr1 == NULL || pStr2 == NULL)
return;
size_t length1 = strlen(pStr1);
size_t length2 = strlen(pStr2);
if(length1 == 0 || length2 == 0 || !(row < length1 && col < length2))
return;
// kLeftUp implies a char in the LCS is found
if(LCS_direction[row][col] == kLeftUp)
{
if(row > 0 && col > 0)
LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col - 1);
// print the char
printf("%c", pStr1[row]);
}
else if(LCS_direction[row][col] == kLeft)
{
// move to the left entry in the direction matrix
if(col > 0)
LCS_Print(LCS_direction, pStr1, pStr2, row, col - 1);
}
else if(LCS_direction[row][col] == kUp)
{
// move to the up entry in the direction matrix
if(row > 0)
LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
char* pStr1="abcde";
char* pStr2="acde";
LCS(pStr1,pStr2);
printf("\n");
system("pause");
return 0;
}</iostream>
代码三:
#include <iostream>
using namespace std;
/* 滚动数组 */
int dp[2][21]; /* 存储LCS长度 */
char X[21];
char Y[21];
int i, j, k;
void main()
{
cin.getline(X,20);
cin.getline(Y,20);
int xlen = strlen(X);
int ylen = strlen(Y);
for(i = 1; i <= xlen; ++i)
{
k = i & 1;
for(j = 1; j <= ylen; ++j)
{
if(X[i-1] == Y[j-1])
{
dp[k][j] = dp[k^1][j-1] + 1;
}else if(dp[k][j-1] > dp[k^1][j])
{
dp[k][j] = dp[k][j-1];
}else
{
dp[k][j] = dp[k^1][j];
}
}
}
printf("len of LCS is: %d\n", dp[k][ylen]);
}
//只能打印一个最长公共子序列
#include <iostream>
using namespace std;
const int X = 100, Y = 100; //串的最大长度
char result[X+1]; //用于保存结果
int count=0; //用于保存公共最长公共子串的个数
/*功能：计算最优值
*参数：
* x:字符串x
* y:字符串y
* b:标志数组
* xlen:字符串x的长度
* ylen:字符串y的长度
*返回值：最长公共子序列的长度
*
*/
int Lcs_Length(string x, string y, int b[][Y+1],int xlen,int ylen)
{
int i = 0;
int j = 0;
int c[X+1][Y+1];
for (i = 0; i<=xlen; i++)
{
c[i][0]=0;
}
for (i = 0; i <= ylen; i++ )
{
c[0][i]=0;
}
for (i = 1; i <= xlen; i++)
{
for (j = 1; j <= ylen; j++)
{
if (x[i - 1] == y[j - 1])
{
c[i][j] = c[i-1][j-1]+1;
b[i][j] = 1;
}
else
if (c[i-1][j] > c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else
if(c[i-1][j] <= c[i][j-1])
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
cout << "计算最优值效果图如下所示：" << endl;
for(i = 1; i <= xlen; i++)
{
for(j = 1; j < ylen; j++)
{
cout << c[i][j] << " ";
}
cout << endl;
}
return c[xlen][ylen];
}
void Display_Lcs(int i, int j, string x, int b[][Y+1],int current_Len)
{
if (i ==0 || j==0)
{
return;
}
if(b[i][j]== 1)
{
current_Len--;
result[current_Len]=x[i- 1];
Display_Lcs(i-1, j-1, x, b, current_Len);
}
else
{
if(b[i][j] == 2)
{
Display_Lcs(i-1, j, x, b, current_Len);
}
else
{
if(b[i][j]==3)
{
Display_Lcs(i, j-1, x, b, current_Len);
}
else
{
Display_Lcs(i-1,j,x,b, current_Len);
}
}
}
}
int main(int argc, char* argv[])
{
string x = "ABCBDAB";
string y = "BDCABA";
int xlen = x.length();
int ylen = y.length();
int b[X + 1][Y + 1];
int lcs_max_len = Lcs_Length( x, y, b, xlen,ylen );
cout << lcs_max_len << endl;
Display_Lcs( xlen, ylen, x, b, lcs_max_len );
//打印结果如下所示
for(int i = 0; i < lcs_max_len; i++)
{
cout << result[i];
}
cout << endl;
return 0;
}
代码四：
<pre name="code" class="cpp">//求取所有的最长公共子序列
#include <iostream>
using namespace std;
const int X = 100, Y = 100; //串的最大长度
char result[X+1]; //用于保存结果
int count=0; //用于保存公共最长公共子串的个数
/*功能：计算最优值
*参数：
* x:字符串x
* y:字符串y
* b:标志数组
* xlen:字符串x的长度
* ylen:字符串y的长度
*返回值：最长公共子序列的长度
*
*/
int Lcs_Length(string x, string y, int b[][Y+1],int xlen,int ylen)
{
int i = 0;
int j = 0;
int c[X+1][Y+1];
for (i = 0; i<=xlen; i++)
{
c[i][0]=0;
}
for (i = 0; i <= ylen; i++ )
{
c[0][i]=0;
}
for (i = 1; i <= xlen; i++)
{
for (j = 1; j <= ylen; j++)
{
if (x[i - 1] == y[j - 1])
{
c[i][j] = c[i-1][j-1]+1;
b[i][j] = 1;
}
else
if (c[i-1][j] > c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else
if(c[i-1][j] < c[i][j-1])
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
else
{
c[i][j] = c[i][j-1]; //或者c[i][j]=c[i-1][j];
b[i][j] = 4;
}
}
}
cout << "计算最优值效果图如下所示：" << endl;
for(i = 1; i <= xlen; i++)
{
for(j = 1; j < ylen; j++)
{
cout << c[i][j] << " ";
}
cout << endl;
}
return c[xlen][ylen];
}
/*功能：计算最长公共子序列
*参数：
* xlen:字符串x的长度
* ylen:字符串y的长度
* x :字符串x
* b:标志数组
* current_len:当前长度
* lcs_max_len:最长公共子序列长度
*
*/
void Display_Lcs(int i, int j, string x, int b[][Y+1],int current_len,int lcs_max_len)
{
if (i ==0 || j==0)
{
for(int s=0; s < lcs_max_len; s++)
{
cout << result[s];
}
cout<<endl;
count++;
return;
}
if(b[i][j]== 1)
{
current_len--;
result[current_len]=x[i- 1];
Display_Lcs(i-1, j-1, x, b,current_len,lcs_max_len);
}
else
{
if(b[i][j] == 2)
{
Display_Lcs(i-1, j, x, b,current_len,lcs_max_len);
}
else
{
if(b[i][j]==3)
{
Display_Lcs(i, j-1, x, b,current_len,lcs_max_len);
}
else
{
Display_Lcs(i,j-1,x,b,current_len,lcs_max_len);
Display_Lcs(i-1,j,x,b,current_len,lcs_max_len);
}
}
}
}
int main(int argc, char* argv[])
{
string x = "ABCBDAB";
string y = "BDCABA";
int xlen = x.length();
int ylen = y.length();
int b[X + 1][Y + 1];
int lcs_max_len = Lcs_Length( x, y, b, xlen,ylen );
cout << lcs_max_len << endl;
Display_Lcs( xlen, ylen, x, b, lcs_max_len, lcs_max_len );
cout << "共有：" << count << "种";
return 0;
}