A linear space algorithm for computing maximal common subsequences 论文
1975Communications of the ACM引用 1105
Algorithms and Data CompressionNetwork Packet Processing and Optimizationsemigroups and automata theory
摘要
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.