- 1、本文档共6页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
最长公共子序列详解论文
最长公共子序列
计科7班 许晴 2012030236
1、问题描述
最长公共子序列是一个十分实用的问题,它可以描述两段文字之间的“相似度”,即它们的雷同程度,从而能够用来辨别抄袭。对一段文字进行修改之后,计算改动前后文字的最长公共子序列,将除此子序列外的部分提取出来,这种方法判断修改的部分,往往十分准确。
2、问题分析及推导过程
根据问题分析的结果,具体的算法设计思路如下:
申明两个数组,用于保存比较的两个字符串;由于事先不知字符串大小,故动态的实现,这里用C++的容器。
申明全局变量,二维数组B和数组C。数组C用于保存计算Xi和Yi的LCS值;数组B保存当前的C是从哪个子问题得来的。为此,定义一个枚举类型,用于标识不同的方向,分别为对角线、向上、向左和向左向上四个方向。
根据动态规划,实现一个函数LCS_LENGTH,完成的功能是计算数组B和C。具体过程是:先是动态申请二维数组B和C,他们的行列长度都增加1,目的就是方便计算。将C的第0行和第0列都赋上0,即初始化。开始计算C[i][j],以行为主,一次计算C的每一个元素,即将两个数组逐一比较。比较时就有两种情况,分别是若相等时,就将C[i][j]设置成C[i-1][j-1],同时将B[i][j]设置成DIAGONAL。若不相等时,比较C[i-1][j] 和 C[i][j-1]的值,又有三种情况:一是C[i-1][j] 与 C[i][j-1]相等, 就随便把某一个赋给C[i][j],比如 C[i-1][j],B[i][j]设置为UP_LEFT;二是若C[i-1][j] 大于 C[i][j-1],则将C[i-1][j]赋给C[i][j],并且将B[i][j]设置成UP;最后是若C[i-1][j] 小于 C[i][j-1],则将C[i][j-1]赋给C[i][j],并且将B[i][j]设置成LEFT。
根据第 3)步骤的结果,就可以找出所有LCS了。这里会用到回溯方法,具体实现可以用栈,也可以用递归。本人使用的是递归,代码简单、易懂。具体实现方法是:申请一个数组用于保存一个LCS,这个数组会反复使用,因此,一旦找到一个就会立即将它输出。再设置一个变量curpos标识当前的数组下标,一个变量len保存当前LCS数组的元素个数。扫描二维数组B,从最后一个开始,判断B的值,有四种情况:当B的值是UP时,就向上递归;当B的值是LEFT时,就向左递归;当B的值是向上或是向左时,这是存在两个选择,先左后上,或是先上后左;当B的值是对角线的时,此时LCS数组才保存当前的字符,len加1,继续沿对角线递归,递归完之后,len减1,回溯。若len为LCS的长度时,就输出。
3、计算求解过程及算法实现
#include iostream
#include cstring
#include fstream
#include vector
#include iterator
using namespace std;
int **C,**B;//C保存计算Xi和Yi的LCS值;B保存当前的C是从哪个子问题得来的
char *LCS;//保存一个最长公共子序列
int len = 0;//回溯时用到的统计保存LCS数组当前长度
enum {DIAGONAL,UP,LEFT,UP_LEFT};
//定义方向,分别是:对角线、向上、向左和向左向上
/*LCS_LENGTH函数,求出数组C和B*/
void LCS_LENGTH(vector char X,vector char Y,int m, int n)//计算C
{
C = new int*[m];//动态分配二维数组
B = new int*[m];
for(int i = 0; i m; i++)
{
C[i] = new int[n];
B[i] = new int[n];
}
for(i = 1;i m;i++)//赋初值,第0列
C[i][0] = 0;
for(int j = 0;j n;j++)//第0行
C[0][j] = 0;
for(i = 1;i m;i++)//开始计算
{
for (j = 1;j n;j++)
{
if(X.at(i-1) == Y.at(j-1))//此下标与数组的下标差1,相等时
{
C[i][j] = C[i-1][j-1] +1;//左上角的LCS+1
B[i][j] = DIAGONAL;
}
else //不相等
{
if(C[i-1][j] == C[i][j-1])//up和left
{
C[i][j] = C[i-1][j];
B[i][j] = UP_L
您可能关注的文档
- 数学论文1.doc
- 数学模型结课论文.doc
- 数学文化与经济学的联系.docx
- 数据分析(梅长林)第1章习题答案.docx
- 数学实验作业2.doc
- 数据包捕获与解析.doc
- 数据库第五章结构化程序设计.doc
- 数据库题作业.doc
- 数据库系统应用与开发--实验一.doc
- 数据结构--05数组的基本操作.doc
- [专精特新]金华永和氟化工有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]重庆升光电力印务有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]无锡巨力重工股份有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]江西凯安新材料集团股份有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]浙江永昌电气股份有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]苏州中创铝业有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]杭州汽轮铸锻有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]浙江美声智能系统有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]汕头市虹桥包装实业有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]江西亚中电子科技股份有限公司行业竞争力评级分析报告(2023版).pdf
最近下载
- 2023河南郑州航空港经济综合实验区管委会招聘14人高频笔试、历年难易点考题(共500题含答案解析)模拟试卷.docx
- 2024-2030年中国双皮奶市场专题研究及市场前景预测评估报告.docx
- abaqus中英菜单对照.docx VIP
- AI技术在提高课堂效率中的应用教学研究课题报告.docx
- 10S505柔性接口给水管道支墩图集.docx
- 2023-2024年中医肛肠学(副高)考试高频题库(历年考点版)带答案解析篇.docx VIP
- 2023年中医肛肠学(副高)历年考试高频考点试题带答案解析.docx VIP
- 2023-2024年中医肛肠学(副高)考试高频题库(历年考点版)带答案解析版.docx VIP
- 2023-2024年中医肛肠学(副高)考试参考题库(历年高频考点版)带答案解析篇.docx VIP
- 七年语文《世说新语》二则课内外文言文比较阅读(原卷版+解析版).docx VIP
文档评论(0)