⌘+K

Pulse Explore Communities Researchers Journals

Home Communities Explore

June 1, 1975Communications of the ACMOpen Access

A linear space algorithm for computing maximal common subsequences

D. S. Hirschberg

View Full Paper

Ask AI

Bookmark

Share

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.

Discussion

No takes yet. Share an insight, caveat, or question.

Cite This Study

D. S. Hirschberg (1975) studied this question.

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

View Full Paper

Ask AI

Bookmark

Share

Keep reading

Synapse has enriched 5 related papers. Consider them for comparative context:

1The String-to-String Correction ProblemOriginal Research · 1974 · 3,035 citations
2Bounds on the complexity of the longest common subsequence problemOriginal Research · 1974 · 22 citations
3Agency as a New Organizing Abstraction for Computer ScienceCommunications of the ACM · Wed,
4A Research Agenda for the Economics of Transformative AICommunications of the ACM · Wed,
5How Immigration and Federal Funding Sustain American AI LeadershipCommunications of the ACM · Tue,

More from Communications of the ACM

A New Era for Inside RisksTue,
Considering AI’s Dependence On Human AgencyMon,
Teaching Novice Computing and Programming in the Agentic AI EraMon,
Is Recursive Self-Improvement Really Here?Fri,
Tailoring Elective Courses to Enhance Women’s Participation in ComputingThu,