A linear space algorithm for computing maximal common subsequences

19751,101 citationsJournal Articlebronze Open Access

Authors

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.

Topics & Keywords

Algorithms and Data Compression Network Packet Processing and Optimization semigroups and automata theory

Publication Details

Published in: Communications of the ACM

Volume 18, Issue 6, pp. 341-343

DOI: 10.1145/360825.360861

Field-Weighted Citation Impact: 13.57

Command Palette

A linear space algorithm for computing maximal common subsequences

Authors

Abstract

Topics & Keywords

Publication Details