三序列之最長共同子序列問題

The Longest Common Subsequence Problem for Three Sequences

吳承育(Chen-Yu Wu)

指導教授 ： 黃光璿

國立暨南國際大學/科技學院/資訊工程學系/碩士(2012年)

https://doi.org/10.6837/NCNU.2012.00236

摘要

三個序列A, B, C長度分別為m, n, h，最長共同子序列問題是在這三個序列中找出最長的共同子序列U。在這篇論文裡，我們會提出一個演算法在O(mnl)時間內來解三序列的最長共同子序列問題，其中l是這三個序列的最長共同子序列長度。

關鍵字

最長共同子序列 ； 最長遞增子序列 ； 動態規畫

並列摘要

Given three sequences A[1:m], B[1:n] and C[1:h], the longest common subsequence problem is finding a sequence U such that U is a common subsequence of A[1:m], B[1:n], C[1:h] and the length of U is maximum. Without loss of
generality, we assume h≧n≧m. In this paper, we present an algorithm to solve the longest common subsequence for three sequences in O(mnl) time where l is the length of U.

並列關鍵字

Longest Common Subsequence ； Longest Increasing Subsequence ； Dynamic Programming

參考文獻

[1] Hirschberg D.S. Aho, A. V. and J.D Ullman. Bounds on the complexity of the longest common subsequence problem. Ann. Symp. on switching and Automata Theory, pages 104{109, 1974.

[2] Hirschberg D.S. Ullman J.D. Aho, A. V. Bounds on the complexity of the longest common subsequence problem. Journal of the ACM, 23(1), 1976.

[3] A. Apostolico. Improving the worst-case performance of the hunt-szymanski strategy for the longest commpn subsequence of two strings. Inform. Process. Lett, 23, 1986.

[4] S. Bespamyatnikh and M. Segal. Enumerating longest increasing subsequences and patience sorting. Inform. Process. Lett, 76:7{11, 2000.

[5] M. Fredman. On computing the length of the longest increasing subsequence. Discrete Math, 11:29{35, 1977.