The longest common subsequence problem revisited
This paper re-examines, in a unified framework, two classic approaches to the problem of finding a longest common subsequence (LCS) of two strings, and proposes faster implementations for both. Let \(\ell\) be the length of an LCS between two strings of length m and \(n\geq m\), respectively, and let s be the alphabet size. The first revised strategy follows the paradigm of a previous \(O(\ell n)\) time algorithm by Hirschberg. The new version can be implemented in time \(O(\ell m\cdot \min \{\log s, \log m, \log(2n/m)\})\), which is profitable when the input strings differ considerably in size (a looser bound for both versions is \(O(mn)\)). The second strategy improves on the Hunt-Szymanski algorithm. This latter takes time \(O((r+n)\log n)\), where \(r\leq mn\) is the total number of matches between the two input strings. Such a performance is quite good \((O(n \log n))\) when \(r\sim n\), but it degrades to \(\Theta(mn \log n)\) in the worst case. On the other hand the variation presented here is never worse than linear-time in the product mn. The exact time bound derived for this second algorithm is \(O(m \log n+d \log (2mn/d))\), where \(d\leq r\) is the number of dominant matches (elsewhere referred to as minimal candidates) between the two strings. Both algorithms require an \(O(n \log s)\) preprocessing that is nearly standard for the LCS problem, and they make use of simple and handy auxiliary data structures.
- Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
- scientific article; zbMATH DE number 1998339
- New algorithms for the LCS problem
- scientific article; zbMATH DE number 842125
- Fast linear-space computations of longest common subsequences
- A fast algorithm for computing longest common subsequences
- A Fast Merging Algorithm
- A faster algorithm computing string edit distances
- A linear space algorithm for computing maximal common subsequences
- A representation for linear lists with movable fingers
- Algorithms for the Longest Common Subsequence Problem
- An almost optimal algorithm for unbounded searching
- Bounds on the Complexity of the Longest Common Subsequence Problem
- Data structures and algorithms 1: Sorting and searching. Transl. from the German
- Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
- New algorithms for the LCS problem
- Preserving order in a forest in less than logarithmic time and linear space
- The String-to-String Correction Problem
- Semi-local longest common subsequences in subquadratic time
- Sparse LCS common substring alignment
- 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
- New algorithms for the LCS problem
- Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
- An \(O(ND)\) difference algorithm and its variations
- The set LCS problem
- Data structures and algorithms for approximate string matching
- Fast linear-space computations of longest common subsequences
- Dynamic programming with convexity, concavity and sparsity
- The shortest common nonsubsequence problem is NP-complete
- Matching for run-length encoded strings
- Performance analysis of some simple heuristics for computing longest common subsequences
- Multi-subsequence searching
- An efficient algorithm for LCS problem between two arbitrary sequences
- About the design of oligo-chips
- How hard is computing the edit distance?
- Compact recognizers of episode sequences
- The longest common subsequence problem for sequences with nested arc annotations.
- A data structure for substring-substring LCS length queries
- Efficient algorithms for the longest common subsequence in \(k\)-length substrings
- Tight conditional lower bounds for longest common increasing subsequence
- Maximal common subsequence algorithms
- Anytime algorithms for the longest common palindromic subsequence problem
- Weighted approximate parameterized string matching
- An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
- An all-substrings common subsequence algorithm
- Finding longest increasing and common subsequences in streaming data
- Searching subsequences
- Two algorithms for LCS consecutive suffix alignment
- Efficient computation of all longest common subsequences
- The longest common subsequence problem for arc-annotated sequences
- Fast Algorithms for Local Similarity Queries in Two Sequences
- Longest common subsequence in at least k length order-isomorphic substrings
- A new practical linear space algorithm for the longest common subsequence problem
- All Semi-local Longest Common Subsequences in Subquadratic Time
- The Constrained Longest Common Subsequence Problem for Degenerate Strings
- Fast Algorithms for Computing Tree LCS
- On the Longest Common Parameterized Subsequence
- A fast longest common subsequence algorithm for similar strings
- Algorithms for two versions of LCS problem for indeterminate strings
- LCS Approximation via Embedding into Local Non-repetitive Strings
- scientific article; zbMATH DE number 3900178 (Why is no real title available?)
- Variants of constrained longest common subsequence
- Longest common subsequence from fragments via sparse dynamic programming
- scientific article; zbMATH DE number 1998339 (Why is no real title available?)
- Sparse Dynamic Programming for Longest Common Subsequence from Fragments
- Multivariate fine-grained complexity of longest common subsequence
- On the Set LCS and Set-Set LCS Problems
- A Probabilistic Analysis of a String Editing Problem and its Variations
- scientific article; zbMATH DE number 842125 (Why is no real title available?)
- Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
- On the generalized constrained longest common subsequence problems
- Algorithms for the longest common subsequence problem for multiple strings based on geometric maxima
- How hard is to compute the edit distance
- Sketching, streaming, and fine-grained complexity of (weighted) LCS
- Longest common subsequences
- Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier
- The longest filled common subsequence problem
- Tight conditional lower bounds for longest common increasing subsequence
- Maximal common subsequence algorithms
- Computing longest common square subsequences
- Fitness landscape analysis for the no-wait flow-shop scheduling problem
- Constrained sequence analysis algorithms in computational biology
- scientific article; zbMATH DE number 5873671 (Why is no real title available?)
- A learning algorithm for the longest common subsequence problem
- scientific article; zbMATH DE number 7651110 (Why is no real title available?)
- New refinement techniques for longest common subsequence algorithms.
- Repetition-free longest common subsequence
- A Linear-Time n 0.4 -Approximation for Longest Common Subsequence
- Linear-space S-table algorithms for the longest common subsequence problem
- The colored longest common prefix array computed via sequential scans
- Cyclic longest common subsequence
- Longest Square Subsequence Problem Revisited
- Edit distance of finite state transducers
- The generalized constrained longest common subsequence in the run-length encoded format
- Efficient algorithms for enumerating maximal common subsequences of two strings
- LCS approximation via embedding into locally non-repetitive strings
- A linear-time \(n^{0.4}\)-approximation for longest common subsequence
- Linear-space LCS enumeration for two strings
- Fast algorithms for computing tree LCS
- Dynamic programming algorithms for the mosaic longest common subsequence problem
- Calculating distances for dissimilar strings: the shortest path formulation revisited
- Thermodynamical approach to the longest common subsequence problem
- Semi-local string comparison: algorithmic techniques and applications
- Finding the longest common subsequence for multiple biological sequences by ant colony optimization
- Finding common structured patterns in linear graphs
This page was built for publication: The longest common subsequence problem revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1098310)