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

摘要

在带约束的最长公共子序列问题中提出一种特殊的新问题:假设有两序列Q和C,Q中指定的匹配位置序列I,计算两序列Q和C的最长公共子序列,且这个最长公共子序列的匹配路径必须经过位置序列I.针对此问题,该文提出一种带匹配路径约束的最长公共子序列算法.首先定义带匹配路径约束的最长公共子序列模型,其次推出该序列的性质,最后求出带匹配路径约束的最长公共子序列长度的基础算法和快速算法.基础算法和快速算法时间复杂度分别为O(mnt)和O(mn),m,n,t分别为序列Q,C,I的长度.%A special new problem is proposed in the constrained longest common subsequence problem. Given sequencesQ , C and the specific positions sequenceI inQ, the matching path constrained longest common subsequence problem forQ andC with respect toI is to find a Longest Common Subsequence (LCS) ofQ andC such that the positionsI inQ are in matching path of this LCS. A matching path constrained longest common subsequence algorithm is proposed for this problem. Firstly, a new model is defined for matching path constrained longest common subsequence. Secondly, the property of the subsequence is given. Lastly, a common method with O(mnt) time and a fast method withO(mn) time are respectively analyzed, wheren,m andt are lengths ofQ,C, andI respectively.