A linear space algorithm for computing maximal common subsequences

1975/06/01 by D. S. Hirschberg · 9 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Network Packet Processing and Optimization #semigroups and automata theory #Longest common subsequence problem #Subsequence #Longest increasing subsequence #Space (punctuation) #Quadratic equation #Algorithm #Linear space #Mathematics #Computer science #Spacetime #Time complexity #Combinatorics #Discrete mathematics #Mathematical analysis

paper · pdf · doi:10.1145/360825.360861

openalex publication_date 1975/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

The problem of finding a longest common subsequence of two strings has been solved in quadratic time and space. An algorithm is presented which will solve this problem in quadratic time and in linear space.

Citations

• The String-to-String Correction Problem

Cited by

• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• A survey of longest common subsequence algorithms
• The Complexity of Some Problems on Subsequences and Supersequences
• Cache-Oblivious Dynamic Programming for Bioinformatics
• Efficient Algorithms with Asymmetric Read and Write Costs
• Longest Common Subsequence in k-length substrings
• Preprint: Exploring Inevitable Waypoints for Unsolvability Explanation in Hybrid Planning Problems
• Longest common subsequence [wikipedia]