Efficient merged longest common subsequence algorithms for similar sequences

摘要

AbstractGiven a pair of merging sequencesA,Band a target sequenceT, the merged longest common subsequence (MLCS) problem is to find out the longest common subsequence (LCS) between sequencesE(A,B)andT, whereE(A,B)is obtained from merging two subsequences ofAandB. In this paper, we first propose an algorithm for solving the MLCS problem inO(n|Σ|+(r?L+1)Lm)time andO(n|Σ|+Lm)space, whererandLdenote the lengths ofTand MLCS, respectively, andmandndenote the shorter and longer lengths ofAandB, respectively. From the time complexity, it is clear that our algorithm is very efficient whenTandE(A,B)are very similar. With slight modification, our algorithm can also solve another merged LCS problem variant, the block-merged LCS (BMLCS) problem, inO(n|Σ|+(r?L+1)Lδ)time andO(n|Σ|+Lδ)space, where