Communications of the ACM · 1975 · 1.1K citations · 3 references
Mathematical ProgrammingLongest Common SubsequenceLinear SpaceEngineeringData MiningString-searching AlgorithmString ProcessingQuadratic TimeCombinatorial Pattern MatchingKnowledge DiscoveryComputational ComplexityLinear Space AlgorithmComputer SciencePattern MatchingCombinatorial OptimizationSublinear Algorithm
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.
3