Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings (Q1085982): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Bounds on the Complexity of the Longest Common Subsequence Problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A representation for linear lists with movable fingers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Fast Merging Algorithm / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithms for the Longest Common Subsequence Problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A linear space algorithm for computing maximal common subsequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A fast algorithm for computing longest common subsequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3219751 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Preserving order in a forest in less than logarithmic time and linear space / rank | |||
Normal rank |
Latest revision as of 18:07, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings |
scientific article |
Statements
Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings (English)
0 references
1986
0 references
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.
0 references
design and analysis of algorithms
0 references
dictionaries
0 references
finger-trees
0 references
efficient merging of linear lists
0 references