Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
type: Item
instance of: scholarly article
title: Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
zbMATH Open document ID: 0608.68057
DOI: 10.1016/0020-0190(86)90044-X
published in: Information Processing Letters
publication date: 1986-01-01T00:00:00Z
review text: Among the algorithms set up to date for finding the longest common subsequence of two strings, the one by \textit{J. W. Hunt} and \textit{T. G. Szymanski} [Commun. ACM 20, 350-353 (1977; Zbl 0354.68078)] exhibits the best known performance in favorable cases, but can be worse than any straightforward algorithm for a large variety of inputs. The new algorithm presented here pursues a schedule of primitive operations quite close to the one inherent to the Hunt-Szymanski strategy, but with substantially enhanced efficiency. In fact, the new algorithm improves on the former in two important respects. First, its worst case is never worse than linear in the product nm of the lengths of the two input strings. Second, its time bound does not always grow with the cardinality r of the set R of all pairs of matching positions of the input strings. Rather, it depends on the cardinality d of a specific subset of R, whose elements are called here dominant matches, and are elsewhere referred to as minimal candidates. This second improvement also appears of significance, since it seems that whenever r gets too close to mn, this forces d to be linear in m. The new algorithm requires standard preprocessing, and makes use of finger-trees. In a forthcoming paper, it will be shown among other things that the same performance can be achieved with simpler and handier auxiliary data structures.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3984595
zbMATH Keywords: design and analysis of algorithms
zbMATH Keywords: dictionaries
zbMATH Keywords: finger-trees
zbMATH Keywords: efficient merging of linear lists
author: Alberto Apostolico
MaRDI profile type: Publication
cites work: Bounds on the Complexity of the Longest Common Subsequence Problem
cites work: A representation for linear lists with movable fingers
cites work: A Fast Merging Algorithm
cites work: Algorithms for the Longest Common Subsequence Problem
cites work: A linear space algorithm for computing maximal common subsequences
cites work: A fast algorithm for computing longest common subsequences
cites work: Q3219751
cites work: Preserving order in a forest in less than logarithmic time and linear space
description: scientific article; zbMATH DE number 3984595