## 留言板

 引用本文: 王前东*. 一种带匹配路径约束的最长公共子序列长度算法[J]. 电子与信息学报, 2017, 39(11): 2615-2619.
WANG Qiandong. A Matching Path Constrained Longest Common Subsequence Length Algorithm[J]. Journal of Electronics and Information Technology, 2017, 39(11): 2615-2619. doi: 10.11999/JEIT170092
 Citation: WANG Qiandong. A Matching Path Constrained Longest Common Subsequence Length Algorithm[J]. Journal of Electronics and Information Technology, 2017, 39(11): 2615-2619.

## A Matching Path Constrained Longest Common Subsequence Length Algorithm

• 摘要: 在带约束的最长公共子序列问题中提出一种特殊的新问题：假设有两序列Q和C, Q中指定的匹配位置序列I，计算两序列Q和C的最长公共子序列，且这个最长公共子序列的匹配路径必须经过位置序列I。针对此问题，该文提出一种带匹配路径约束的最长公共子序列算法。首先定义带匹配路径约束的最长公共子序列模型，其次推出该序列的性质，最后求出带匹配路径约束的最长公共子序列长度的基础算法和快速算法。基础算法和快速算法时间复杂度分别为O(mnt)和O(mn), m, n, t分别为序列Q, C, I的长度。
•  [1] WANG Haoxin, ZHONG Jingdong, and ZHANG Defu. A duplicate code checking algorithm for the programming experiment[C]. 2015 Second International Conference on Mathematics and Computers in Sciences and in Industry (MCSI), Sliema, 2015: 39-42. doi:  10.1109/MCSI.2015.12. [2] WANGGER R A and FISCHER M J. The string-to-string correction problem[J]. Journal of the Association for Computing Machinery, 1974, 21(1): 168-173. [3] 赵建军, 陈滨, 杨利斌, 等. 一种基于字符串模型的轨迹相似度计算[J]. 科学技术与工程, 2013, 13(1): 80-84. [4] ZHAO Jianjun, CHEN Bin, YANG Libin, et al. Measure similarity between trajectories based on alphabetic string model[J]. Science Technology and Engineering, 2013, 13(1): 80-84. [5] TSAI Y T. The constrained longest common subsequence problem[J]. Information Processing Letters, 2003, 88(4): 173-176. doi:  10.1016/j.ipl.2003.07.001. [6] GOTTHILF Z, HTSAI YERMELIN D, and LEWENSTEIN M. Constrained LCS: Hardness and approximation[C]. Proceedings of the 19th Annual Symposium on Combinatorial Pattern Matching, Berlin, 2008: 255-262. doi:  10.1007/978-3-540-69068-9_24. [7] CHIN F, SANTIS A, FERRARA A, et al. A simple algorithm for the constrained sequence problems[J]. Information Processing Letters, 2004, 90(4): 175-179. doi: 10.1016/j.ipl. 2004.02.008. [8] ARSLAN A and EGECIOGLU O. Algorithms for the constrained longest common subsequence problems[J]. International Journal of Foundations of Computer Science, 2005, 16(6): 1099-1109. doi:  10.1142/S0129054105003674. [9] BECERRA D, SOTO W, NINO L, et al. An algorithm for constrained LCS[C]. IEEE/ACS International Conference on Computer Systems and Applications, Hammamet Tunisia, 2010: 1-7. doi:  10.1109/AICCSA.2010.5586937. [10] BONIZZONI P, VEDOVA G, DONDI R, et al. Variants of constrained longest common subsequence[J]. Information Processing Letters, 2010, 110(20): 877-881. doi: 10.1016/j.ipl. 2010.07.015. [11] 业宁, 朱大铭, 张倩倩, 等. 带约束最长公共子序列快速算法[J]. 南京大学学报(自然科学版), 2009, 45(5): 576-584. [12] YE Ning, ZHU Daming, ZHANG Qianqian, et al. Fast algorithm of the longest common subsequence with constraints[J]. Journal of Nanjing Universitv, 2009, 45(5): 576-584. [13] TSENG C T, YANG C B, and ANN H Y. Efficient algorithms for the longest common subsequence problem with sequential substring constraints[J]. Journal of Complexity, 2013, 29(1): 44-52. doi:  10.1109/BIBE.2011.34. [14] 魏龙翔, 何小海, 滕奇志, 等. 结合Hausdorff距离和最长公共子序列的轨迹分类[J]. 电子与信息学报, 2013, 35(4): 784-790. doi:  10.3724/SP.J.1146.2012.01078. [15] WEI Longxiang, HE Xiaohai, TENG Qizhi, et al. Trajectory classification based on Hausdorff distance and longest common subsequence[J]. Journal of Electronics Information Technology, 2013, 35(4): 784-790. doi: 10.3724/ SP.J.1146.2012.01078. [16] BEAL R, AFRIN T, FARHEEN A, et al. A new algorithm for the LCS problem with application in compressing genome resequencing data[C]. 2015 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), Washington, DC, 2015: 69-74. doi:  10.1109/BIBM.2015.7359657. [17] LIU Richen, GUO Hanqi, ZHANG Jiang, et al. Comparative visualization of vector field ensembles based on longest common subsequence[C]. 2016 IEEE Pacific Visualization Symposium (PacificVis), Taipei, 2016: 96-103. doi: 10.1109/ PACIFICVIS.2016.7465256.
•  [1] 彭佳林, 揭萍.  基于序列间先验约束和多视角信息融合的肝脏CT图像分割, 电子与信息学报. doi: 10.11999/JEIT170933 [2] 田增山, 王向勇, 周牧, 李玲霞.  基于DBSCAN子空间匹配的蜂窝网室内指纹定位算法, 电子与信息学报. doi: 10.11999/JEIT160768 [3] 孙宁霄, 吴琼之, 孙林.  基于局部最优匹配的斜视SAR子孔径成像算法, 电子与信息学报. doi: 10.11999/JEIT170466 [4] 李海洋, 王恒远.  基于TL1范数约束的子空间聚类方法, 电子与信息学报. doi: 10.11999/JEIT170193 [5] 崔文岩, 孟相如, 杨欢欢, 李纪真, 陈天平, 康巧燕.  QoS约束的链路故障多备份路径恢复算法, 电子与信息学报. doi: 10.11999/JEIT151230 [6] 范庆辉, 卢红喜, 保铮, 肖春宝.  基于半正定约束的极化相似度最优模型匹配目标分解, 电子与信息学报. doi: 10.11999/JEIT141468 [7] 张文林, 张连海, 陈琦, 李弼程.  语音识别中基于低秩约束的本征音子说话人自适应方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.00848 [8] 赵烨, 蒋建国, 洪日昌.  基于空间约束的快速鲁棒特征匹配优化, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.01960 [9] 魏龙翔, 何小海, 滕奇志, 高明亮.  结合Hausdorff距离和最长公共子序列的轨迹分类, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.01078 [10] 孙海青, 王小青, 种劲松.  基于SAR子孔径序列图像配准的海洋动态信息获取, 电子与信息学报. doi: 10.3724/SP.J.1146.2011.00478 [11] 唐永鹤, 卢焕章, 胡谋法.  基于SCCH特征描述子的图像匹配算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2011.00007 [12] 彭来献, 恽姿, 赵文栋, 田畅.  一种基于最长队列预测的CICQ交换结构调度算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2009.00908 [13] 王睿, 方勇.  基于2-D公共因子的精确提取的图像盲复原方法, 电子与信息学报. doi: 10.3724/SP.J.1146.2007.00994 [14] 孟艳, 汪晋宽, 朱俊.  基于子空间的线性约束最小二乘恒模算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2007.01191 [15] 高月红, 张欣, 杨大成.  一种用于CDMA反向链路的公共速率控制算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2005.01559 [16] 张晓, 吴启晖, 时兆武.  自适应跳频受约束的信令跳变序列设计, 电子与信息学报. doi: 10.3724/SP.J.1146.2006.00632 [17] 孙暐, 吴镇扬, 刘海滨.  非线性统计匹配用于子带鲁棒语音识别, 电子与信息学报. [18] 徐信, 蔡跃明, 徐友云.  基于训练序列的发射分集OFDM系统的空时子空间幅度跟踪信道估计, 电子与信息学报. [19] 刘东, 相敬林.  多族谐波信号估计的子空间匹配投影算法, 电子与信息学报. [20] 常义林, 李兵兵, 李飞鹏.  一种用于序列图象位移估值的匹配函数比特位相关匹配函数, 电子与信息学报.
• 点击查看大图
##### 计量
• 文章访问数:  374
• HTML全文浏览量:  43
• PDF下载量:  213
• 被引次数: 0
##### 出版历程
• 收稿日期:  2017-01-23
• 修回日期:  2017-08-19
• 刊出日期:  2017-11-19

### 目录

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈

官方微信，欢迎关注