New algorithms for the LCS problem (Q1072704)

The LCS problem is to determine a longest common subsequence (LCS) of two symbol sequences. Two algorithms which improve two existing results, respectively, are presented. Let m, n be the lengths of the two input strings, with \(M\leq n\), \(\rho\) being the length of the LCS, and s being the number of distinct symbols appearing in the two strings. It is shown that the first algorithm presented requires at most \(O(n \log s)\) preprocessing time and \(O(\rho m \log(n/m)+\rho m)\) processing time to solve the problem. This bound is better than that of previous algorithms especially when n is much greater than m. The algorithm also exhibits desirable properties under conditions of sparse matches. The second scheme achieves essentially the same bound \((O(\rho m \log(n/\rho)+\rho m))\) by employing efficient merging methods in the computations. It also outperforms existing algorithms designed for sparsely-matched situations. Together, the two algorithms provide interesting contrasts of different approaches to one problem; they also offer improved alternatives for actual implementation.