The longest common subsequence problem revisited

DOI10.1007/BF01840365zbMath0636.68083MaRDI QIDQ1098310

Alberto Apostolico, Concettina Guerra

Publication date: 1987

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

longest common subsequenceefficient merging of linear lists

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

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