1975 ALinearSpaceAlgForCompMaxComSub

• (Hirshberg, 1975) ⇒ Dan S. Hirschberg. (1975). “A Linear Space Algorithm for Computing Maximal Common Subsequences.” Communications of the ACM, 18(6). doi:10.1145/360825.360861.

Subject Headings: Longest Common Subsequence Task, Longest Common Subsequence Algorithm.

Cited By

• ~747 http://scholar.google.com/scholar?q=%22A+Linear+Space+Algorithm+for+Computing+Maximal+Common+Subsequences%22+1975

Quotes

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.

---

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
1975 ALinearSpaceAlgForCompMaxComSub	Dan S. Hirschberg			A Linear Space Algorithm for Computing Maximal Common Subsequences			http://www.cs.zju.edu.cn/people/yedeshi/Alinearspace-p341-hirschberg.pdf	10.1145/360825.360861		1975