An Improved Algorithm For Approximate String Matching
Authors:
- Zvi GalilZGZvi Galil
- Kunsoo ParkKPKunsoo Park
- 1 December 1990
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 19 (6) , 989-999
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 upon the known algorithms.Keywords
This publication has 9 references indexed in Scilit:
- Fast parallel and serial approximate string matchingJournal of Algorithms, 1989
- Fast string matching with k differencesJournal of Computer and System Sciences, 1988
- Data structures and algorithms for approximate string matchingJournal of Complexity, 1988
- Improved string matching with k mismatchesACM SIGACT News, 1986
- Algorithms for approximate string matchingInformation and Control, 1985
- An O(n log n) algorithm for finding all repetitions in a stringJournal of Algorithms, 1984
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977
- An Extension of the String-to-String Correction ProblemJournal of the ACM, 1975
- The String-to-String Correction ProblemJournal of the ACM, 1974