Pulse Journal Club Trending Explore Questions Researchers

Download the App

Join discussions, follow papers, and never miss your next session.

© Synapse Social LLC, 2026Privacy Policy

Home Explore Journal Club Trending

⌘+K

A linear space algorithm for computing maximal common subsequences | Synapse

June 1, 1975Open Access

A linear space algorithm for computing maximal common subsequences

Key Points

Key points are not available for this paper at this time.

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.

Mark Helpful

Bookmark

Relay

View Full Paper

Cite This Study

D. S. Hirschberg (Sun,) studied this question.

synapsesocial.com/papers/6a08d3b527ceb0c2a2d60029 https://doi.org/https://doi.org/10.1145/360825.360861

Mark Helpful

Bookmark

Relay

View Full Paper

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

1Bounds on the complexity of the longest common subsequence problem1974 · 15 citations
2Bounds for the String Editing Problem1976 · 123 citations
3The String-to-String Correction Problem1974 · 3,061 citations
4Selected combinatorial research problems.1972 · 77 citations
5Spelling correction in systems programs1970 · 106 citations