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

Two algorithms to solve longest circular common subsequence problems

作　　者：郑子君 王洪 余成[2] Zheng Zijun;Wang Hong;Yu Cheng(College of Mechanical Engineering,Chongqing University of Technology,Chongqing 400054,China;College of Hehai,Chongqing Jiaotong University,Chongqing 400074,China)

机构地区：[1]重庆理工大学机械工程学院,重庆400054 [2]重庆交通大学河海学院,重庆400074

出　　处：《计算机应用研究》2020年第11期3334-3337,3358,共5页Application Research of Computers

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

摘　　要：最长循环公共子序列(LCCS)是两个字符串在所有可能的循环移位操作下能得到的最长公共子序列(LCS)。针对穷举移位量求解LCCS效率过低的问题,设法对候选移位量进行筛选。通过证明循环移位操作对两字符串间LCS长度增量影响的上下限,得到最优移位量的必要条件,从而减小了求解LCCS的枚举量;在此基础上,建立了求解LCCS的迭代方法,只经过少数几次迭代便可消除绝大部分无效候选移位量;此外,还提出一个可在O(mn)时间复杂度下快速估算LCCS长度的近似算法。大量随机模拟表明,当两字符串间的相似度明显高于随机字符串的相似度时,提出的两种算法表现良好。Longest common circular subsequence(LCCS)is the longest common subsequence(LCS)of two strings with any possible circular shifting.Finding the LCS for every possible circular shifting mount is the simplest approach to solve LCCS problem,but it is very inefficient.This paper established a necessary condition for the optimum shifting amount by estimating the upper and lower bounds of the LCS length increment after a circular shifting,and thus established an iterative filtering algorithm to solve LCCS problem.This algorithm could eliminate most of the invalid candidates in several iteration according to the tests.This paper provided an approximate algorithm estimate the length of LCCS even faster,which worked with a time com-plexity of O(mn).Stochastic tests show that both proposed algorithms work very well if the similarity between the given strings is sufficiently higher than that between two random strings.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]