Fast linear-space computations of longest common subsequences

DOI10.1016/0304-3975(92)90132-YzbMath0747.68019OpenAlexW2023784545MaRDI QIDQ1190449

S. Singh

Publication date: 26 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90132-y

zbMATH Keywords

longest common subsequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Related Items (8)

DERIVING A FAST SYSTOLIC ALGORITHM FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM ⋮ Longest common subsequences ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ Variants of constrained longest common subsequence ⋮ Fast linear-space computations of longest common subsequences ⋮ Unnamed Item ⋮ Simple and fast linear space computation of longest common subsequences ⋮ APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †

Cites Work

• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• The longest common subsequence problem revisited
• An \(O(ND)\) difference algorithm and its variations
• 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 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
• Algorithms for the Longest Common Subsequence Problem
• The String-to-String Correction Problem
• A representation for linear lists with movable fingers
• Unnamed Item
• Unnamed Item

This page was built for publication: Fast linear-space computations of longest common subsequences