Communications of the ACM · 1975 · 1.1K citations · 3 references
ComputingComputer ScienceAlgorithmsSequence AnalysisComputational ComplexitySequence MiningSequence Similarity SearchSpace ComplexityString AlgorithmsComplexity Of String AlgorithmsLongest Common SubsequenceLongest Common SubstringPattern Matching AlgorithmsString SearchString Searching
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
The String-to-String Correction Problem
Robert A. Wagner, Michael J. Fischer · Journal of the ACM · 1974 · 3.1K citations · Full text
Selected combinatorial research problems.
Václav Chvátal, David A. Klarner, Donald E. Knuth · 1972 · 77 citations