An improved algorithm for approximate string matching
Lecture notes in computer sciencePublished 1 January 1989
Zvi Galil, Kunsoo Park
Citations33
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Given a text string, a pattern string, and an integer k, a new algorithm for finding all occurrences of the pattern string in the text string with at most k differences is presented. Both its theoretical and practical variants improve the known algorithms.
Keywords
Computer Science
Journal of the ACMThe String-to-String Correction Problem
3,063 Citations1974Robert A. Wagner, Michael J. Fischer
An algorithm is presented which solves the string-to-string correction problem in time proportional to the product of the lengths of the two strings.
SIAM Journal on ComputingFast Pattern Matching in Strings
2,917 Citations1977Donald E. Knuth, James H. Morris +1 more
An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings, showing that the set of concatenations of even palindromes, i.e., the language $\{\alpha \alpha ^R\}^*$, can be recognized in linear time.
Information and ControlAlgorithms for approximate string matching
621 Citations1985Esko Ukkonen
An improved algorithm that works in time and in space O and algorithms that can be used in conjunction with extended edit operation sets, including, for example, transposition of adjacent characters.
Journal of AlgorithmsFast parallel and serial approximate string matching
333 Citations1989Gad M. Landau, Uzi Vishkin
Given a text of lenght n, a pattern of length m and an integer k, this work presents parallel and serial algorthms for finding all occurrences of the pattern in the text with at most k differences.
Journal of the ACMAn Extension of the String-to-String Correction Problem
318 Citations1975Robert A. Wagner, Roy Lowrance
The set of allowable edit operations is extended to include the operation of interchanging the positions of two adjacent characters under certain restrictions on edit-operation costs, and it is shown that the extended problem can still be solved in time proportional to the product of the lengths of the given strings.
Journal of AlgorithmsAn O(n log n) algorithm for finding all repetitions in a string
258 Citations1984Michael G. Main, Richard J. Lorentz
An O(n log n) algorithm is presented to find all repetitions in a string of lenght n, which uses a variation of the Knuth-Morris-Pratt algorithm to finding all partial occurrences of a pattern within a text string.
Journal of Computer and System SciencesFast string matching with k differences
195 Citations1988Gad M. Landau, Uzi Vishkin
This work presents an algorithm for finding all occurrences of the pattern in the text, each with at most k differences, given a text of length n, a pattern of length m, and an integer k.
Journal of ComplexityData structures and algorithms for approximate string matching
142 Citations1988Zvi Galil, Raffaele Giancarlo
This paper surveys techniques for designing efficient sequential and parallel approximate string matching algorithms and special attention is given to the methods for the construction of data structures that efficiently support primitive operations needed in approximatestring matching.
ACM SIGACT NewsImproved string matching with k mismatches
112 Citations1986Zvi Galil, Raffaele Giancarlo
A compact version of the authors' algorithm for string matching with k mismatches, achieving a time performance of 0(mlogm+kn) for general alphabets and of 0 (m+ Kn) for alphabet s whose size is fixed.