2000 · 69 citations · 26 references
ComputingComputer ScienceAlgorithmsComputational LinguisticsNatural Language ProcessingError DetectionPattern RecognitionSearching AlgorithmsString AlgorithmsText MiningComplexity Of String AlgorithmsPattern MatchingPattern Matching AlgorithmsString SearchString Searching
The string matching with mismatches problem is that of finding the number of mismatches between pattern P of length m and every length m substring of the text T . Currently, the best algorithms for this problem are the following. The Landau-Vishkin algorithm finds all locations where the pattern has at most k errors (where k is part of the input) in time O(nk). The Abrahamson algorithm finds the number of mismatches at every location in time O(n p m log m). We present an algorithm that is faster than both. Our algorithm finds all locations where the pattern has at most k errors in time O(n p k log k). We also show an algorithm that solves the above problem in time O((n + nk 3 m ) log k). 1 Introduction String matching, the problem of finding all occurrences of a given pattern in a given text, is a classical problem in computer science. The problem has pleasing theoretical features and a number of direct applications to "real world" problems. The Boyer-Moore [8] algorit...
26
Binary codes capable of correcting deletions, insertions and reversals
V.I. Levenshtein · Soviet physics. Doklady · 1965 · 10.4K citations
Fast Pattern Matching in Strings
Donald E. Knuth, James H. Morris, Vaughan Pratt · SIAM Journal on Computing · 1977 · 2.9K citations
Alfred V. Aho, Margaret J. Corasick · Communications of the ACM · 1975 · 2.9K citations · Full text
A fast string searching algorithm
Robert S. Boyer, J Strother Moore · Communications of the ACM · 1977 · 2.3K citations · Full text
Linear pattern matching algorithms
Peter Weiner · 1973 · 1.8K citations