[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
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;
}
