字符串的最长公共子序列问题 (二)

根据公式可以得知C[i,j]保存当前(Xi,Yi)的最大子序列长度
知道了最长公共子序列的长度，下一步就是考虑如何输出这个序列
为了输出子序列我们需要增加一个数组pos[i,j]
pos[i,j]用来保存C[i,j]的解是由哪一个子问题的解得到的
有三种情况：
1:
c[i,j]:=c[i-1,j-1]+1;
pos[i,j]:=" ";
2:
c[i,j]:=c[i-1,j];
pos[i,j]:="↑";
3:
c[i,j]:=c[i,j-1];
pos[i,j]:="←"
构造子序列时：
从pos[m,n]开始向前扫描：
1.当pos[i,j]中遇到" "时（意味着xi=yi是LCS的一个元素），
表示Xi与Yj的最长公共子序列是由Xi-1与Yj-1的最长公共子序列在尾部加上xi得到的子序列；
2.当pos[i,j]中遇到"↑"时，表示Xi与Yj的最长公共子序列和Xi-1与Yj的最长公共子序列相同；
3.当pos[i,j]中遇到"←"时，表示Xi与Yj的最长公共子序列和Xi与Yj-1的最长公共子序列相同。

*/
#include "stdafx.h"
#include
using namespace std;
void ConstructLCS(int **pos,const char *str,int length1,int length2);
void LCS(const char* str1,const char* str2,int length1,int length2)
{
//初始化工作,动态创建两个二维数组
int **c=new int *[length1+1];
int **pos=new int *[length1+1];
for(int i=0;i {
c[i]=new int[length2+1];
pos[i]=new int[length2+1];
}
for(int i=0;i c[i][0]=0;
for(int j=0;j c[0][j]=0;

//0 代表
//1 代表 ↑
//2 代表 ←
for(int i=1;i<=length1;i++)
for(int j=1;j<=length2;j++)
{
if(str1[i-1]==str2[j-1])
{
c[i][j]=c[i-1][j-1]+1;
pos[i][j]=0;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
pos[i][j]=1;
}
else
{
c[i][j]=c[i][j-1];
pos[i][j]=2;
}
}
cout<<"最长公共子序列长度："< cout<<"最长公共子序列是：";
ConstructLCS(pos,str1,length1,length2);
cout< }
//构造最长子序列
void ConstructLCS(int **pos,const char *str,int length1,int length2)
{
if(length1==0||length2==0)
return;
if(pos[length1][length2]==0)
{
ConstructLCS(pos,str,length1-1,length2-1);
cout< }
else if(pos[length1][length2]==1)
ConstructLCS(pos,str,length1-1,length2);
else if(pos[length1][length2]==2)
ConstructLCS(pos,str,length1,length2-1);
}

int _tmain(int argc, _TCHAR* argv[])
{
char *str1="abcefghkjl";
char *str2="bfhjkjl";
LCS(str1,str2,10,7);
system("pause");
return 0;
}