计算机应用研究

作者：郑子君,王洪,余成,

单位：1.重庆理工大学机械工程学院,重庆400054；2.重庆交通大学河海学院,重庆400074；

关键词：最长公共子序列,循环字符串,文本相似度,动态规划,

基金：国家自然科学基金青年项目(11702046)；重庆市教委科学研究项目(KJ1600910)；；

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

来源：2020年第11期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2020年第11期