The longest common subsequence problem revisited
From MaRDI portal
Publication:1098310
DOI10.1007/BF01840365zbMath0636.68083MaRDI QIDQ1098310
Alberto Apostolico, Concettina Guerra
Publication date: 1987
Published in: Algorithmica (Search for Journal in Brave)
Related Items (40)
Performance analysis of some simple heuristics for computing longest common subsequences ⋮ How hard is to compute the edit distance ⋮ Searching subsequences ⋮ Data structures and algorithms for approximate string matching ⋮ Calculating distances for dissimilar strings: the shortest path formulation revisited ⋮ Two algorithms for LCS consecutive suffix alignment ⋮ Weighted approximate parameterized string matching ⋮ Longest common subsequences ⋮ Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier ⋮ Fast Algorithms for Local Similarity Queries in Two Sequences ⋮ A Probabilistic Analysis of a String Editing Problem and its Variations ⋮ A Linear-Time n 0.4 -Approximation for Longest Common Subsequence ⋮ Variants of constrained longest common subsequence ⋮ Fast Algorithms for Computing Tree LCS ⋮ An efficient algorithm for LCS problem between two arbitrary sequences ⋮ An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints ⋮ Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion ⋮ On the generalized constrained longest common subsequence problems ⋮ Fast linear-space computations of longest common subsequences ⋮ Dynamic programming with convexity, concavity and sparsity ⋮ Finding the longest common subsequence for multiple biological sequences by ant colony optimization ⋮ Fitness landscape analysis for the no-wait flow-shop scheduling problem ⋮ Constrained sequence analysis algorithms in computational biology ⋮ Efficient algorithms for the longest common subsequence in \(k\)-length substrings ⋮ An all-substrings common subsequence algorithm ⋮ About the design of oligo-chips ⋮ Finding common structured patterns in linear graphs ⋮ Unnamed Item ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Finding longest increasing and common subsequences in streaming data ⋮ LCS approximation via embedding into locally non-repetitive strings ⋮ Unnamed Item ⋮ Fast algorithms for computing tree LCS ⋮ Unnamed Item ⋮ LCS Approximation via Embedding into Local Non-repetitive Strings ⋮ Sparse LCS common substring alignment ⋮ Multi-subsequence searching ⋮ How hard is computing the edit distance? ⋮ Compact recognizers of episode sequences ⋮ A data structure for substring-substring LCS length queries
Cites Work
- Unnamed Item
- New algorithms for the LCS problem
- Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
- A faster algorithm computing string edit distances
- An almost optimal algorithm for unbounded searching
- 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
- The String-to-String Correction Problem
- A representation for linear lists with movable fingers
This page was built for publication: The longest common subsequence problem revisited
