第五次实验报告
——最长公共子序列的生成算法
1.1算法应用背景
最长公共子序列是一个序列S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的。
最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。
1.2算法原理
若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
例：∑= {x, y, z} ，A = x y z y x z x z
x x x 是长度为3 的子序列
x z y z x 是长度为5 的子序列
例：A = x y z y x z x z，B = x z y x x y z x
x x x是长度为3 的公共子序列
x z y z 是长度为4 的公共子序列
x z y x x z 是长度为6 的最长公共子序列
1.3算法描述
记L n,m为序列A n和B m的最长公共子序列长度，则L i,j为序列A i和Bj的最长公共子序列的长度。根据最长公共子序列的性质，则得到：
阶段的划分和最长公共子序列长度的获取
第一阶段：计算A1和Bj的最长公共子序列的长度L1,j ,j=1,2,…m
第二阶段：计算A2和B j的最长公共子序列的长度L2,j, j=1,2,…m
第n 阶段：计算A n和B j的最长公共子序列的长度L n,j, j=1,2,…m
第n 阶段的L m,n便是序列A n和B m的最长公共子序列的长度
为了得到A n和B m最长公共子序列，设置一个二维的状态字数组s i，j，在上述每一个阶段计算L n,j过程中，根据公共子序列的性质则有按照如下方法把搜索状态登记于状态字s i，j中：s i，j =1 a i=b j
s i，j =2 a i≠b j L i-1,j>= L i,j-1
s i，j =3 a i≠b j L i-1,j< L i,j-1
设L n,m=k,S k=c1c2……c k是序列A n和B m的长度为k的最长公共子序列。最长公共子序列的搜索过程为状态字s n，m开始。搜索过程如下：
S m,n =1 a n=b m c k=a n下一个搜索方向是S n-1,m-1
S m,n =2 a i≠b j L i-1,j>= L i,j-1下一个搜索方向是S n-1,m
S m,n =3 a i≠b j L i-1,j< L i,j-1 下一个搜索方向是S n,m-1
递推关系：
若s i，j =1 则c k=a i，i=i-1，j=j-1，k=k-1
s i，j =2 a i≠b j 则i=i-1
s i，j =3 a i≠b j 则j=j-1
从i=n，j=m开始搜索，直到i=0或j=0结束，即可得到A n和B m的最长公共子序列。1.4程序实现及程序截图
1.4.1程序源码
#include
#include
#define MAXLEN 100
void LCSLength(char *x, char *y, char *z,int m, int n, int c[][MAXLEN], int b[][MAXLEN]) {
int i,j,k,len;
for(i = 0; i <= m; i++)
c[i][0] = 0;
for(j = 1; j <= n; j++)
c[0][j] = 0;
for(i = 1; i<= m; i++)
{
for(j = 1; j <= n; 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
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
i=m;j=n;k=len=c[i][j];
while ((i!= 0) &&(j != 0))
{ // printf("%d %d\n",i,j);
switch (b[i][j])
{
case 1: z[k]=x[i-1];k--;j--;
case 2:i--;break;
case 3:j--;break;
}
}
printf("最长公共子序列长度\n");
for (i=1;i<=m;i++){
for (j=1;j<=n;j++){
printf("%d ",c[i][j]);
}
printf("\n");
}
printf("最长公共子序列字符比较\n"); for (i=1;i<=m;i++){
for (j=1;j<=n;j++){
printf("%d ",b[i][j]);
