《计算机应用研究》|Application Research of Computers

求解最长循环公共子序列问题的两个算法

Two algorithms to solve longest circular common subsequence problems

免费全文下载 (已被下载 次)  
获取PDF全文
作者 郑子君,王洪,余成
机构 重庆理工大学 机械工程学院;重庆交通大学 河海学院
统计 摘要被查看 次,已被下载
摘要 最长循环公共子序列(LCCS)是两个字符串在所有可能的循环移位操作下能得到的最长公共子序列(LCS)。针对穷举移位量求解LCCS效率过低的问题,设法对候选移位量进行筛选。通过证明循环移位操作对两字符串间LCS长度增量影响的上下限,得到最优移位量的必要条件,从而减小了求解LCCS的枚举量;在此基础上,建立了求解LCCS的迭代方法,只经过少数几次迭代便可消除绝大部分无效候选移位量;此外,还提出一个可在O(mn)的时间复杂度下快速估算LCCS的长度的近似算法。大量随机模拟表明,当两字符串间的相似度明显高于随机字符串的相似度时,提出的两种算法表现良好。
关键词 最长公共子序列;循环字符串;文本相似度;动态规划
基金项目 国家自然科学基金青年项目(11702046)
重庆市教委科学研究项目(KJ1600910)
本文URL http://www.arocmag.com/article/02-2020-11-007.html
收稿日期
修回日期
页码 -
中图分类号 TP301.6
文献标志码