| 摘要: |
| 在最长填充公共子序列问题中提出一种新问题：假设有一个完整序列獵和一个不完整序列玅，长度分别为玬和n，玅中丢失的元素为相邻的相同元素，要求寻找一个丢失前的序列，使得獵和具有最长的公共子序列。针对此问题，首先将玅中每个元素复制玬-1个并插入玅中原来的位置，生成长度为玬n的扩展序列玅*，然后证明了獵和Q的最长扩展公共子序列是两序列獵和Q*的最长公共子序列，最后提出一种时空复杂度为玂(mn)的最长扩展公共子序列求解新算法，并用轨迹实验证明了该算法对强噪声干扰和轨迹点丢失的同时有效性。 |
| 关键词: 最长公共子序列（LCS） 最长填充公共子序列（LFCS） 扩展公共子序列（ECS） 最长扩展公共子序列（LECS） |
| DOI：10.20079/j.issn.1001-893x.230717004 |
|
| 基金项目: |
|
| A New Algorithm Longest Extended Common Subsequence |
| WANG Qiandong |
| (Southwest China Institute of Electronic Technology,Chengdu 610036,China) |
| Abstract: |
| A new problem is proposed in the longest filled common subsequence problem.Given a complete sequence 獵 with the length of 玬 and an incomplete sequence 玅 with the length of 玭 obtained by deleting some adjacent same elements from |
| Key words: longest common subsequence(LCS) longest filled common subsequence(LFCS) extended common subsequence(ECS) longest extended common subsequence(LECS) |
