LCS问题的一种新算法及其推广

A NEW ALGORITHM FOR COMPUTING LONGEST COMMON SUBSEQUENCES AND ITS EXTENSION

求解LCS(Longest Common Subsequences)的通常算法,空间和时间的复杂性为O(n^2)。本文中提出的算法,空间复杂性为O(n),时间复杂性为O(n)～O(n^2),时间复杂性取决于序列中符号的分布,本算法便于并行处理及制成微处理器。 为了应用于模式识别,推广到WLCS(Weighted Longest Common Subsequences)以及LCSM(Longest Common Submatrix)。 给出了有关的定理,及算法正确性的证明。

In this paper a new algorithm for computing longest common subsequences of two given sequences (or strings) is presented, by which the problem is solved in running time of 0(n)-O(n2) and in storage space of O(n), where n is the length of sequences. Running time depends upon the distribution of characters (or symbols) on the sequences. This algorithm is the first to make parallel processing of the LCS possible, and it is suitable for VLSI technology, as its hardware realization is quite easy. On the other hand, the best running time of the algorithms by other authors for finding the LCS has a relation to O(nlog n)-O(n2 log n), while the storage space bears generally a relation to O(n2). All of them do not take into account of the distribution of characters and they can not perform the parallel process. Thus the average performance of the algorithm in this paper is much better than that of other algorithms.The theorem and the proof of correctness related to the new algorithm is also briefly stated. For an application to the pattern recognition, a discussion is made on its extension to the weighted longest common subsequences and to the longest common sub-matrix.