Longest common subsequences

DOI10.1007/3-540-58338-6_63zbMath1493.68284OpenAlexW1948141881MaRDI QIDQ5096874

Vlado Dančík, Mike S. Paterson

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1994 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58338-6_63

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items (10)

Deposition and extension approach to find longest common subsequence for thousands of long sequences ⋮ A faster linear systolic algorithm for recovering a longest common subsequence ⋮ Computing the similarity of two sequences with nested arc annotations ⋮ Asymptotic expected number of base pairs in optimal secondary structure for random RNA using the Nussinov--Jacobson energy model ⋮ Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier ⋮ Letter change bias and local uniqueness in optimal sequence alignments ⋮ A hybrid genetic algorithm for the repetition free longest common subsequence problem ⋮ Approximation to the mean curve in the LCS problem ⋮ Constrained sequence analysis algorithms in computational biology ⋮ On longest matching consecutive subsequence

Cites Work

• New algorithms for the LCS problem
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• The longest common subsequence problem revisited
• A linear space algorithm for the LCS problem
• A faster algorithm computing string edit distances
• A longest common subsequence algorithm suitable for similar text strings
• Fast linear-space computations of longest common subsequences
• A variational problem for random Young tableaux
• An information-theoretic lower bound for the longest common subsequence problem
• Some limit results for longest common subsequences
• Maximal common subsequences and minimal common supersequences
• Searching subsequences
• Algorithms for approximate string matching
• A linear space algorithm for computing maximal common subsequences
• Longest common subsequences of two random sequences
• Bounds for the String Editing Problem
• Bounds on the Complexity of the Longest Common Subsequence Problem
• A fast algorithm for computing longest common subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• Algorithms for the Longest Common Subsequence Problem
• Sparse dynamic programming I
• The String-to-String Correction Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Longest common subsequences