最长公共子序列算法,最长公共子序列论文2,最长公共子序列问题,最长公共子序列代码 易达学习网 > 最长公共子序列论文 > 最长公共子序列算法,最长公共子序列论文2,最长公共子序列问题,最长公共子序列代码 正文

最长公共子序列算法,最长公共子序列论文2,最长公共子序列问题,最长公共子序列代码

发布时间:2013-07-21 来源: 最长公共子序列论文

求取两个长度为 n 的字符串的 最长公共子序列 (LCS)问题,利用(57 )策 略可以有效... 最长公共子序列 的并行 算法 ","会议论文","... 一种基于 LCS 的相似网页检测 算...

最长公共子序列 13 计科行知班 张宗雷 2013 一、问题描述 一个序列的子序列:该序列删除若干子序列后得到的序列。

最长公共子序列:

给定两个子序列 X 和 Y 当另一个序列 Z 既是 X 的子序列又是 Y 的子序列 则称 Z 是 X 和 Y 的公共子序列。当 Z 是最长的一个公共子序列时 Z 称为 X 和 Y 的最长公 共子序列。

二、问题分析及推导过程 1. 申明两个数组,用于保存比较的两个字符串;由于事先不知字符串大小,故动态的 实现,这里用 C++的容器。

2. 申明全局变量,二维数组 B 和数组 C。数组 C 用于保存计算 Xi 和 Yi 的 LCS 值; 数组 B 保存当前的 C 是从哪个子问题得来的。为此,定义一个枚举类型,用于标 识不同的方向,分别为对角线、向上、向左和向左向上四个方向。

3. 根据动态规划,实现一个函数 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。

4. 根据第 3)步骤的结果,就可以找出所有 LCS 了。这里会用到回溯方法,具体实 现可以用栈,也可以用递归。本人使用的是递归,代码简单、易懂。具体实现方法 是:申请一个数组用于保存一个 LCS,这个数组会反复使用,因此,一旦找到一 个就会立即将它输出。再设置一个变量 curpos 标识当前的数组下标,一个变量 len 保存当前 LCS 数组的元素个数。扫描二维数组 B,从最后一个开始,判断 B 的值, 有四种情况:

当 B 的值是 UP 时, 就向上递归; 当 B 的值是 LEFT 时, 就向左递归; 当 B 的值是向上或是向左时,这是存在两个选择,先左后上,或是先上后左;当 B 的值是对角线的时,此时 LCS 数组才保存当前的字符,len 加 1,继续沿对角线递 归,递归完之后,len 减 1,回溯。若 len 为 LCS 的长度时,就输出。

三、计算求解过程及算法实现 #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_LEFT;

} else if(C[i-1][j] >

C[i][j-1])//up { C[i][j] = C[i-1][j];

B[i][j] = UP;

} else//left { C[i][j] = C[i][j-1];

B[i][j] = LEFT;

} } } } } /*Print_LCS 函数,打印出所有的 LCS*/ void Print_LCS(int **B,vector <char>

X,int i,int j,int curpos,int maxLCS,ostream &out) { if(i >= 0 &&

j >= 0) { if(len == maxLCS)//已经找到一个 LCS,则输出 { for(int k = len-1;k >= 0;k--) out<<LCS[k];

out<<endl;

} else { if(B[i][j] == DIAGONAL)//对角线 { LCS[curpos] = X.at(i-1);

len++;

Print_LCS(B,X,i-1,j-1,curpos+1,maxLCS,out);

len--;//回溯 } else if(B[i][j] == UP)//向上 { Print_LCS(B,X,i-1,j,curpos,maxLCS,out);

} else if(B[i][j] == LEFT)//向左 { Print_LCS(B,X,i,j-1,curpos,maxLCS,out);

} else//向上或向左 { Print_LCS(B,X,i-1,j,curpos,maxLCS,out);//向上 Print_LCS(B,X,i,j-1,curpos,maxLCS,out);//向左 } } } } /*输出字符串*/ void out(vector<char>::iterator beg, vector<char>::iterator end) { while(beg != end) cout<<*beg++; cout<<endl;

} int main() { char s;

vector <char>

X, Y;

ifstream fin("LCS.in");//输入文件 //char X[MAXSIZE],Y[MAXSIZE];

int count = 0;//实验的测试组数 cout<<"Reading the file LCS.in..."<<endl;

if(fin == NULL) { cout<<"Reading failed!"<<endl;

cout<<"There is no input file!"<<endl;

cout<<"Please make a iuput file use name LCS.in and input strings."<<endl;

} else { cout<<"Reading succeed!"<<endl;

fin>>count;

fin.get(s);//过滤一个换行符 cout<<"These are "<<count<<"

groups to be tested!"<<endl;

for(int z = 1;z <= count;z++) { while(fin.get(s) &&

s != '\n') X.push_back(s);

while (fin.get(s)&&

s!= '\n') Y.push_back(s);

cout<<"The group "<<z<<":"<<endl;

out(X.begin(), X.end());

out(Y.begin(), Y.end());

int m = X.size()+1;

int n = Y.size()+1;

LCS_LENGTH(X,Y,m,n);

int max = C[m-1][n-1];//保存 LCS 的长度 if(0 == max)//没有最长公共子序列 { cout<<"There is no Longest Common Subsequence!\n"<<endl;

} else { LCS = new char[max];

cout<<"All the Longest Common Subsequence are:"<<endl; Print_LCS(B,X,m-1,n-1,0,max,cout);

cout<<endl;

for(int i = 0;i <

m;i++)//释放空间 { delete []B[i];

delete []C[i];

} delete []B;

delete []C;

delete []LCS;

} X.clear();

Y.clear();

}//for } return 0;

} 四、运行结果 五、计算复杂性分析 如果仅要求出一个 LCS 的长度,而不需要构造一个 LCS 的元素,则只需要 c 的两行:

正在被计算的一行和前面一行,也就是说完全可以用 2*min(m,n)项以及 O(1)的额外空 间来计算一个 LCS 的长度。 此时首先要比较出 m,n 的大小, 利用他们而这种较小的作为存储空间的行, 在本次程序 中构造了两个数组 vector<long>

Common1,Common;利用 Common 来存储正要计算的 i 行和利用 Common1 来存储需要用到的 i-1 行,计算结束后,便将本行计算结果 Common 中 的值赋给上一行 Common1,此时 Common1 中存储的便是 i 行中的计算结果, 然后 Common 便可以继续利用 Common1 中存储的值,来急需计算 i+1 行。

然而,实际上,需要的辅助空间还可以更小(仅略多于表 c 一行的空间) ,为 min(m,n) 项以及 O(1)的额外空间。

这是因为在实际的计算 i 行第 j 个值的过程中,仅用到了 i-1 行中第 j 和 j-1 个值,所以只要 用两个变量及时给出 i-1 行中第 j 和 j-1 个的值即可完成计算, 这样便可以进一步缩小所需额 外辅助空间。

最长公共子序列论文2 暂无相关推荐文档 暂无评价 | 0人阅读 | 0次下载 | 举报文档 阅读已结束,如果下载本文需要使用 你可能喜欢 您的评论 *感谢支持,给文档评个星吧! 用户评价 ...

最长公共子序列 (LCS)的问题是计算机科学中一个基本和重要的问题,它是一种仅仅... 并且与之相对应的数值特征及相似性分析使这些直观的视觉感知更加理性化. 在本篇论文...

而最长公共子串(要求连 续)和 最长公共子序列 是不同的. 最长公共子序列 是一个十分... 初步掌握动态规划算法; 二、实验... 16 邵阳学院课程设计(论文)任务书年级专业 题目...

最长公共子序列算法,最长公共子序列论文2,最长公共子序列问题,最长公共子序列代码》出自:易达学习网
链接地址:http://www.wuyida.com/content/s6Ncld6N696fhRVQ.html

相关文章阅读

网站地图 | 关于我们 | 联系我们 | 广告服务 | 免责声明 | 在线留言 | 友情链接 | RSS 订阅 | 热门搜索
版权所有 易达学习网 www.wuyida.com

最长公共子序列算法,最长公共子序列论文2,最长公共子序列问题,最长公共子序列代码