一种带匹配路径约束的最长公共子序列长度算法

摘要：

在带约束的最长公共子序列问题中提出一种特殊的新问题:假设有两序列Q和C,Q中指定的匹配位置序列I,计算两序列Q和C的最长公共子序列,且这个最长公共子序列的匹配路径必须经过位置序列I.针对此问题,该文提出一种带匹配路径约束的最长公共子序列算法.首先定义带匹配路径约束的最长公共子序列模型,其次推出该序列的性质,最后求出带匹配路径约束的最长公共子序列长度的基础算法和快速算法.基础算法和快速算法时间复杂度分别为O(mnt)和O(mn),m,n,t分别为序列Q,C,I的长度.

关键词：最长公共子序列、匹配路径约束、带约束的最长公共子序列、带匹配路径约束的最长公共子序列

所属期刊栏目：39

分类号：TP301(计算技术、计算机技术)

在线出版日期：2017-11-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：2615-2619