最长公共子序列详解论文

《最长公共子序列详解论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、最长公共子序列计科7班许晴20120302361、问题描述最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取山来，这种方法判断修改的部分，往往十分准确。2、问题分析及推导过程根据问题分析的结果，具体的算法没计思路如下：1）申明两个数组，用于保存比较的两个字符申；由于事先不知字符串大小，故动态的实现，这里用C++的容器。2）申明全局变量，二维数组B和数组C。数组C用于保存计算Xi和Yi的LCS值；数组B保存当

2、前的C是从哪个子问题得来的。为此，定义一个枚举类型，用于标识不同的方向，分别为对角线、向上、向左和向左向上四个方向。3）根据动态规划，实现一个函数LCS_LENGTH,完成的功能是计算数组B和C。具体过程是：先是动态申请二维数组B和C，他们的行列长度都增加1，目的就是方便计算。将C的第0行和第0列都赋上0,即初始化。开始计算C[i][j],以行为主，一次计算C的每一个元素，即将两个数组逐一比较。比较时就有两种情况，分别是若相等时，就将C[i]Lj]设置成C[i-l]Lj-l],同时将B[i]Lj]没置成DIAGONAL。若不相等时，比较C[i-l]

3、[j]和C[il[j-1]的值,又有三种情况:一是C[i-l][j]与C[i][j-1]相等，就随便把某一个赋给C[i][j],比如C[i-l][j],设賈为UP_LEFT；-是若C[i-l]U]大于C[i][j-1],则将C[i-l]U]赋给C[i]U]，并且将B[i]U]设置成UP;最后是若c[i-i]u]小于c[i][j-i]，则将赋给c[i]u],并且将B[i][j]设置成LEFT。4）根据第3）步骤的结果，就可以找出所有LCS了。这里会用到回溯方法，具体实现可以用栈，也可以用递归。本人使用的是递归，代码简单、易懂。具体实现方法是：申请一个

4、数组用于保存一个LCS,这个数组会反复使用，因此，一旦找到一个就会立即将它输出。再设置一个变量curpos标识当前的数组下标，一个变量len保存当前LCS数组的元素个数。扫描二维数组B,从最后一个开始，判断B的值,有四种情况：当B的值是UP时，就句上递归；当B的值是LEFT时，就向左递归;当B的值是向上或是向左时，这是存在两个选择，先左后上，或是先上后左；当B的值是对角线的吋，此吋LCS数组才保存当前的字符，len加1，继续沿对角线递归，递归完之后，len减1，回溯。若len为LCS的长度时，就输出。3、计算求解过程及算法实现#include

5、stream>#include#include#include〈vector〉#include〈iterator〉usingnamespacestd;int**C,**B;//C保存计算Xi和Yi的LCS值；B保存当前的C是从哪个子问题得来的char*LCS;//保存一个®长公共子序列intlen=0;//回溯时川到的统计保存LCS数组当前长度enum{DIAGONAL,UP,LEFT,UP_LEFT};//定义方向，分别是：对角线、向上、向左和向左向上/*LCS_LENGTH函数，求出数组C和B*/voidLC

6、S_LENGTH(vectorX,vectorY，intm,intn)//计算C{C=newint*fml;//动态分0d二维数组B=newint*[m];for(inti=0;i

7、组的下标差1,相等时{C[i]Lj]=C[i-1]U-l]+l;//左上角的LCS+1BliJIjJ=DIAGONAL;}else//不相等{if(C[i-l]U]==C[i]Lj-l])//up和left{c[i]o]=c[i-i]u];Bfilfjl=UP_LEFT;}elseif(C[i-l][j]>C[i]lj-l])//up{c[i]u卜c[i-i]u];B[i][j]=UP；}else//leftC[i][j]=C[i][j-l];Bfilfjl=LEFT;/*Print_LCS函数，打印出所有的LCS*/voidPrint_LCS(i

8、ntvectorX,inti,intj,intcurpos,intmaxLCS,ostream&out)(if