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.
Keywords
Longest common subsequence problemSubsequenceLongest increasing subsequenceSpace (punctuation)Quadratic equationAlgorithmLinear spaceMathematicsComputer scienceSpacetimeTime complexityCombinatoricsDiscrete mathematicsMathematical analysis
Affiliated Institutions
Related Publications
Fast Kernels for String and Tree Matching
In this paper we present a new algorithm suitable for matching discrete objects such as strings and trees in linear time, thus obviating dynamic programming with quadratic time ...
A partial solution to the reachability-problem for vector-addition systems
With geometrical techniques we hope to bring new insight into the reachability problem for vector-addition systems, which is pertaining in many areas in computer science theory ...
An Algorithm for the General Petri Net Reachability Problem
An algorithm is presented for the general Petri net reachability problem. It is based on a generalization of the basic reachability tree construction which is made symmetric wit...
Improved time bounds for near-optimal sparse Fourier representations
•We study the problem of finding a Fourier representation <b>R </b>of <i>m</i> terms for a given discrete signal <b>A</b> of length<i> N</i>. The Fast Fourier Transform (FFT) ca...
Publication Info
- Year
- 1975
- Type
- article
- Volume
- 18
- Issue
- 6
- Pages
- 341-343
- Citations
- 1095
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
1095
OpenAlex
Cite This
D. S. Hirschberg
(1975).
A linear space algorithm for computing maximal common subsequences.
Communications of the ACM
, 18
(6)
, 341-343.
https://doi.org/10.1145/360825.360861
Identifiers
- DOI
- 10.1145/360825.360861