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

• 作者: 余成 王洪 郑子君
• 来源期刊: 计算机应用研究
• 关键词: 最长公共子序列 循环字符串 文本相似度 动态规划
• 年，卷（期）: 2020,（11）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 3334-3337,3358
• 页数: 5页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.19734/j.issn.1001-3695.2019.06.0258

摘要

最长循环公共子序列(LCCS)是两个字符串在所有可能的循环移位操作下能得到的最长公共子序列(LCS).针对穷举移位量求解LCCS效率过低的问题,设法对候选移位量进行筛选.通过证明循环移位操作对两字符串间LCS长度增量影响的上下限,得到最优移位量的必要条件,从而减小了求解LCCS的枚举量;在此基础上,建立了求解LCCS的迭代方法,只经过少数几次迭代便可消除绝大部分无效候选移位量;此外,还提出一个可在O(mn)时间复杂度下快速估算LCCS长度的近似算法.大量随机模拟表明,当两字符串间的相似度明显高于随机字符串的相似度时,提出的两种算法表现良好.