×

A new flexible algorithm for the longest common subsequence problem. (English) Zbl 0841.68051

Summary: Given two sequences \(A = a_1a_2 \dots a_m\) and \(B = b_1b_2 \dots b_n\), \(m \leq n\), over some alphabet \(\Sigma\) of size \(s\), the longest common subsequence problem is to find a sequence of greatest possible length, \(p\), that can be obtained from both \(A\) and \(B\) by deleting zero or more (not necessarily adjacent) symbols. A new algorithm that is efficient for both short and long longest common subsequences is presented. It also improves on previous methods for longest common subsequences of intermediate length. Thus, it is more flexible and can be used for a wider range of applications than others. The algorithm is based on the well-known paradigm of computing dominant matches and was obtained by observing additional structural properties leading to a kind of dualization. The worst-case running time of the algorithm is \(O(ns + \min \{pm, p(n - p)\})\). Some experimental results which prove the practicability of the new method are given, too.

MSC:

68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite