【摘要】：在帶約束的最長公共子序列問題中提出一種特殊的新問題:假設(shè)有兩序列Q和C,Q中指定的匹配位置序列I,計(jì)算兩序列Q和C的最長公共子序列,且這個(gè)最長公共子序列的匹配路徑必須經(jīng)過位置序列I。針對(duì)此問題,該文提出一種帶匹配路徑約束的最長公共子序列算法。首先定義帶匹配路徑約束的最長公共子序列模型,其次推出該序列的性質(zhì),最后求出帶匹配路徑約束的最長公共子序列長度的基礎(chǔ)算法和快速算法。基礎(chǔ)算法和快速算法時(shí)間復(fù)雜度分別為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.
【作者單位】： 中國電子科技集團(tuán)公司第十研究所;
【分類號(hào)】：TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 林清波,吳錘紅;求最長公共子序列長度的一個(gè)新方法[J];福建農(nóng)業(yè)大學(xué)學(xué)報(bào);1998年04期

2 方俊初;呂虹;張愛雪;;產(chǎn)生m子序列的一種實(shí)用算法[J];河北工程大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年04期

3 胡曉琳;陳曉云;;基于符號(hào)化表示的時(shí)間序列頻繁子序列挖掘[J];計(jì)算機(jī)工程;2008年10期

4 張力生;楊美潔;雷大江;;時(shí)間序列重要點(diǎn)分割的異常子序列檢測[J];計(jì)算機(jī)科學(xué);2012年05期

5 王防修;周康;;基于最長公共子序列的隨機(jī)路徑選擇算法設(shè)計(jì)[J];計(jì)算機(jī)工程與設(shè)計(jì);2014年06期

6 鄭翠玲;;最長公共子序列算法的分析與實(shí)現(xiàn)[J];武夷學(xué)院學(xué)報(bào);2010年02期

7 王達(dá),榮岡,李鴻亮;一種變步長趨勢子序列搜索算法[J];浙江大學(xué)學(xué)報(bào)(工學(xué)版);2004年12期

8 郭冬梅;;基于狀態(tài)壓縮的最長公共上升子序列快速算法[J];計(jì)算機(jī)技術(shù)與發(fā)展;2014年05期

9 楊海斌;趙學(xué)鋒;王秀花;張利香;;一種求所有最長增量子序列的算法[J];山東大學(xué)學(xué)報(bào)(工學(xué)版);2010年06期

10 李欣,舒風(fēng)笛;最長公共子序列問題的改進(jìn)快速算法[J];計(jì)算機(jī)應(yīng)用研究;2000年02期

相關(guān)會(huì)議論文 前2條

1 劉維;陳];;基于剪枝跳躍技術(shù)的最長公共子序列算法[A];2006年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集[C];2006年

2 倪晟宇;;在流數(shù)據(jù)模式下計(jì)算最長遞增子序列長度[A];2005年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集[C];2005年

相關(guān)重要報(bào)紙文章 前2條

1 ;編程沙龍[N];電腦報(bào);2003年

2 PALADIN;編程沙龍[N];電腦報(bào);2003年

相關(guān)博士學(xué)位論文 前1條

1 王樹林;生物子序列頻數(shù)分布與腫瘤亞型分類模型研究[D];國防科學(xué)技術(shù)大學(xué);2007年

相關(guān)碩士學(xué)位論文 前5條

1 肖鵬;單時(shí)間序列異常子序列檢測算法的研究[D];哈爾濱工業(yè)大學(xué);2016年

2 宗文卓;Hadoop平臺(tái)上多序列最長公共子序列并行算法及應(yīng)用研究[D];廣西大學(xué);2015年

3 趙曉燕;基于多索引的高維時(shí)間序列子序列檢索研究[D];大連理工大學(xué);2010年

4 朱鶴;結(jié)果分級(jí)的快速子序列相似查詢方法研究[D];燕山大學(xué);2010年

5 高鴻遠(yuǎn);基于子序列匹配的壓縮XML查詢[D];哈爾濱工業(yè)大學(xué);2009年

，

本文編號(hào)：2242151