一种最长扩展公共子序列新算法  

A New Algorithm Longest Extended Common Subsequence

作　　者：王前东[1] WANG Qiandong(Southwest China Institute of Electronic Technology,Chengdu 610036,China)

机构地区：[1]中国西南电子技术研究所,成都610036

出　　处：《电讯技术》2024年第8期1307-1314,共8页Telecommunication Engineering

摘　　要：在最长填充公共子序列问题中提出一种新问题:假设有一个完整序列C和一个不完整序列Q,长度分别为m和n,Q中丢失的元素为相邻的相同元素,要求寻找一个丢失前的序列Q,使得C和Q具有最长的公共子序列。针对此问题,首先将Q中每个元素复制m-1个并插入Q中原来的位置,生成长度为mn的扩展序列Q^(*),然后证明了C和Q的最长扩展公共子序列是两序列C和Q^(*)的最长公共子序列,最后提出一种时空复杂度为O(mn)的最长扩展公共子序列求解新算法,并用轨迹实验证明了该算法对强噪声干扰和轨迹点丢失的同时有效性。A new problem is proposed in the longest filled common subsequence problem.Given a complete sequence C with the length of m and an incomplete sequence Q with the length of n obtained by deleting some adjacent same elements from^Q,it is required to seek that the longest extended common subsequence of C and Q is the longest common subsequence of C and^Q.To solve this problem,firstly(m-1)copies of each element in Q are inserted into the original position in Q to generate the extended sequence Q∗with the length of mn.Then,it is proved that the longest extended common subsequence of C and Q is the longest subsequence of C and Q^(∗).Finally,a new algorithm with O(mn)space-time complexity is proposed for the longest extended common subsequence and trajectory experiments show that the algorithm can effectively solve the trajectory similarity measurement problem with strong noise interference and trajectory points loss.

关 键 词：最长公共子序列(LCS) 最长填充公共子序列(LFCS) 扩展公共子序列(ECS) 最长扩展公共子序列(LECS) 

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