An Improved Algorithm For Approximate String Matching
Zvi Galil, Kunsoo Park · SIAM Journal on Computing · 1990
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.
Cited by 169 works. doi:10.1137/0219067
Authors
References
- The String-to-String Correction Problem
- Fast Pattern Matching in Strings
- Algorithms for approximate string matching
- An Extension of the String-to-String Correction Problem
- Fast parallel and serial approximate string matching
- Fast string matching with k differences
- Data structures and algorithms for approximate string matching
- An O(n log n) algorithm for finding all repetitions in a string
- Improved string matching with k mismatches