Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
From MaRDI portal
Publication:1085982
DOI10.1016/0020-0190(86)90044-XzbMath0608.68057MaRDI QIDQ1085982
Publication date: 1986
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items (15)
The longest common subsequence problem revisited ⋮ A lower bound for the edit-distance problem under an arbitrary cost function ⋮ Longest common subsequences ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ A Linear-Time n 0.4 -Approximation for Longest Common Subsequence ⋮ Variants of constrained longest common subsequence ⋮ Fast computation of a longest increasing subsequence and application ⋮ New clique and independent set algorithms for circle graphs ⋮ Fast linear-space computations of longest common subsequences ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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 ⋮ Enumeration of maximal common subsequences between two strings ⋮ A data structure for substring-substring LCS length queries
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
This page was built for publication: Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
