article · 2006

common subsequence problem

Yung-hsing Peng, Hsing-yen Ann, Communicated L. Boasson

Cited by 0Abstract and details only

Abstract

The longest common subsequence (LCS) problem can be used to measure the relationship between sequences. In general, the inputs of the LCS problem are two sequences. For finding the relationship between one sequence and a set of sequences, we cannot apply the traditional LCS algorithms immediately. In this paper, we define the mosaic LCS (MLCS) problem of finding a mosaic sequence C, composed of repeatable k sequences in source sequence set S, such that the LCS of C and the target sequence T is maximal. Based on the concept of break points in sequence T, we first propose a divide-and-conquer algorithm with O(n2m|S|+n3 log k) time for solving this problem, where n and m are the length of T and the maximal length of sequences in S, respectively. Furthermore, an improved algorithm with O(n(m+k)|S|) time is proposed by applying an efficient preprocessing for the MLCS problem.

Cite this paper

APA 7

Peng, Y.-H., Ann, H.-Y., & Boasson, C. L. (2006). common subsequence problem.

MLA 9

Peng, Yung-hsing, et al. “common subsequence problem.” 2006.

Chicago

Peng, Yung-hsing, Hsing-yen Ann, and Communicated L. Boasson. 2006. “common subsequence problem.”

Harvard

Peng, Y.-H., Ann, H.-Y. and Boasson, C.L. (2006) ‘common subsequence problem’.

BibTeX

@article{peng2006common,
  title = {{common subsequence problem}},
  author = {Peng, Yung-hsing and Ann, Hsing-yen and Boasson, Communicated L.},
  year = {2006}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.