一种带匹配路径约束的最长公共子序列长度算法

发布时间：2018-09-14 08:35

【摘要】：在带约束的最长公共子序列问题中提出一种特殊的新问题:假设有两序列Q和C,Q中指定的匹配位置序列I,计算两序列Q和C的最长公共子序列,且这个最长公共子序列的匹配路径必须经过位置序列I。针对此问题,该文提出一种带匹配路径约束的最长公共子序列算法。首先定义带匹配路径约束的最长公共子序列模型,其次推出该序列的性质,最后求出带匹配路径约束的最长公共子序列长度的基础算法和快速算法。基础算法和快速算法时间复杂度分别为O(mnt)和O(mn),m,n,t分别为序列Q,C,I的长度。
[Abstract]:This paper presents a special new problem in the problem of longest common subsequences with constraints: assuming that there are two sequences Q and C assigned matching position sequences I, the longest common subsequences of two sequences Q and C are calculated. And the matching path of the longest common subsequence must pass through the position sequence I. To solve this problem, this paper proposes a longest common subsequence algorithm with matching path constraints. Firstly, the longest common subsequence model with matching path constraints is defined, then the properties of the sequence are deduced. Finally, the basic algorithm and fast algorithm for the length of the longest common subsequence with matching path constraints are obtained. The time complexity of the basic algorithm and the fast algorithm are O (mnt) and O (mn) respectively.
【作者单位】： 中国电子科技集团公司第十研究所;
【分类号】：TP301.6

【相似文献】

相关期刊论文 前10条

1 林清波,吴锤红;求最长公共子序列长度的一个新方法[J];福建农业大学学报;1998年04期

2 方俊初;吕虹;张爱雪;;产生m子序列的一种实用算法[J];河北工程大学学报(自然科学版);2012年04期

3 胡晓琳;陈晓云;;基于符号化表示的时间序列频繁子序列挖掘[J];计算机工程;2008年10期

4 张力生;杨美洁;雷大江;;时间序列重要点分割的异常子序列检测[J];计算机科学;2012年05期

5 王防修;周康;;基于最长公共子序列的随机路径选择算法设计[J];计算机工程与设计;2014年06期

6 郑翠玲;;最长公共子序列算法的分析与实现[J];武夷学院学报;2010年02期

7 王达,荣冈,李鸿亮;一种变步长趋势子序列搜索算法[J];浙江大学学报(工学版);2004年12期

8 郭冬梅;;基于状态压缩的最长公共上升子序列快速算法[J];计算机技术与发展;2014年05期

9 杨海斌;赵学锋;王秀花;张利香;;一种求所有最长增量子序列的算法[J];山东大学学报(工学版);2010年06期

10 李欣,舒风笛;最长公共子序列问题的改进快速算法[J];计算机应用研究;2000年02期

相关会议论文 前2条

1 刘维;陈];;基于剪枝跳跃技术的最长公共子序列算法[A];2006年全国理论计算机科学学术年会论文集[C];2006年

2 倪晟宇;;在流数据模式下计算最长递增子序列长度[A];2005年全国理论计算机科学学术年会论文集[C];2005年

相关重要报纸文章 前2条

1 ;编程沙龙[N];电脑报;2003年

2 PALADIN;编程沙龙[N];电脑报;2003年

相关博士学位论文 前1条

1 王树林;生物子序列频数分布与肿瘤亚型分类模型研究[D];国防科学技术大学;2007年

相关硕士学位论文 前5条

1 肖鹏;单时间序列异常子序列检测算法的研究[D];哈尔滨工业大学;2016年

2 宗文卓;Hadoop平台上多序列最长公共子序列并行算法及应用研究[D];广西大学;2015年

3 赵晓燕;基于多索引的高维时间序列子序列检索研究[D];大连理工大学;2010年

4 朱鹤;结果分级的快速子序列相似查询方法研究[D];燕山大学;2010年

5 高鸿远;基于子序列匹配的压缩XML查询[D];哈尔滨工业大学;2009年

，

本文编号：2242151