字符串的最长公共子序列问题
[cpp]
// 最长公共子序列问题.cpp : Defines the entry point for the console application.
//
/*问题：给出两个字符串，找出它们的最长公共子序列
什么是最长公共子序列？
最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。
其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，
且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
而最长公共子串(要求连续)和最长公共子序列是不同的（可以是不连续的）
例如：
abgfjlmnp
- - - -
afkqln
-- --
它们的最长公共子序列是：afln
思路：
利用动态规划方法
设两个子序列X={x1,x2,x3,...xi},Y={y1,y2,y3,...,yi}
设C[i,j]用来保存Xi和Yj的LCS长度（i=0,1... j=0,1,...）
可以得到递推方程：
__
_| 0 i=0 or j=0
C[i,j]=|_ C[i-1,j-1]+1 i,j>0 and xi=yi
|__ max{C[i,j-1],C[i-1,j]} i,j>0 and xi!=yi
根据公式可以得知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 <iostream>
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<length1+1;i++)
{
c[i]=new int[length2+1];
pos[i]=new int[length2+1];
}
for(int i=0;i<length1+1;i++)
c[i][0]=0;
for(int j=0;j<length2+1;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<<"最长公共子序列长度："<<c[length1][length2]<<endl;
cout<<"最长公共子序列是：";
ConstructLCS(pos,str1,length1,length2);
cout<<endl;
}
//构造最长子序列
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<<str[length1-1];
}
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;
}
// 最长公共子序列问题.cpp : Defines the entry point for the console application.
//
/*问题：给出两个字符串，找出它们的最长公共子序列
什么是最长公共子序列？
最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。
其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，
且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
而最长公共子串(要求连续)和最长公共子序列是不同的（可以是不连续的）
例如：
abgfjlmnp
- - - -
afkqln
-- --
它们的最长公共子序列是：afln
思路：
利用动态规划方法
设两个子序列X={x1,x2,x3,...xi},Y={y1,y2,y3,...,yi}
设C[i,j]用来保存Xi和Yj的LCS长度（i=0,1... j=0,1,...）
可以得到递推方程：
__
_| 0 i=0 or j=0
