Publication | Open Access
A linear space algorithm for computing maximal common subsequences
1.1K
Citations
3
References
1975
Year
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.
| Year | Citations | |
|---|---|---|
Page 1
Page 1