在詢問模式下尋找最長共同子序列問題

The Longest Common Subsequence Problem in the Query-Answer Setting

張喬幃(Chiao-Wei Chang)

指導教授 ： 黃光璿

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

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

摘要

給予兩條序列A = a1a2…am 和B = b1b2…bn，最長共同子序列問題要求找到一條最長子序列，這條子序列要同時是A序列和B序列的共同子序列。在本論文中，我們提出一個方法，可解決在詢問模式下尋找最長共同子序列問題。基於一些假設，在詢問模式下尋找最長共同子序列問題可以在O(mn / log n)時間內被解決，其中m、n分別代表序列A和B的長度。

關鍵字

最長共同子序列 ； 動態規劃 ； 演算法 ； 詢問模式

並列摘要

Given two sequences A = a1a2...am and B = b1b2...bn, the longest common subsequence problem is to find a subsequence such that the subsequence is a common subsequence of A and B and its length is longest. In this paper, we present a method for the longest common subsequence in the query answer setting. Under some assumptions, the problem can be solved in time O(mn / log n) where m, n are the lengths of sequences A and B.

並列關鍵字

Longest Common Subsequence ； Dynamic Programming ； Algorithm ； Query- Answer Setting

參考文獻

[1] A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wiler, "Geometric applications of a matrix-searching algorithm," Algorithmica, Vol. 2, No. 1-4, pp. 195-208, 1987.

[2] A. Aggarwal and J. Park, "Notes on searching in multidimensional monotone arrays," Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, pp. 497-512, 1988.

[3] S. Bespamyatnikh and M. Segal, "Enumerating longst increasing subsequences and patience soring," Information Processing Letters, Vol. 76, pp. 7-11, 2000.

[4] S. Deorowicz, "An algorithm for solving the longest increasing circular subsequence problem," Information Processing Letters, Vol. 19, pp. 630-634, 2009.

[5] O. Gotoh, "An improved algorithm for matching biological sequences," Journal of Molecular Biology, Vol. 162, pp. 705-708, 1982.