Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings

DOI10.1016/0020-0190(86)90044-XzbMath0608.68057MaRDI QIDQ1085982

Alberto Apostolico

Publication date: 1986

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

dictionaries; design and analysis of algorithms; efficient merging of linear lists; finger-trees

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

Related Items

Variants of constrained longest common subsequence, Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence, An almost-linear time and linear space algorithm for the longest common subsequence problem, The longest common subsequence problem revisited, A lower bound for the edit-distance problem under an arbitrary cost function, New clique and independent set algorithms for circle graphs, Fast linear-space computations of longest common subsequences, Efficient merged longest common subsequence algorithms for similar sequences, Fast computation of a longest increasing subsequence and application, Enumeration of maximal common subsequences between two strings, A data structure for substring-substring LCS length queries, Unnamed Item

Cites Work

• Unnamed Item
• Preserving order in a forest in less than logarithmic time and linear space
• A linear space algorithm for computing maximal common subsequences
• Bounds on the Complexity of the Longest Common Subsequence Problem
• A fast algorithm for computing longest common subsequences
• A Fast Merging Algorithm
• Algorithms for the Longest Common Subsequence Problem
• A representation for linear lists with movable fingers