Academic Commons

Reports

An Improved Algorithm for Approximate String Matching

Galil, Zvi; Park, Kunsoo

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.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-468-89
Published Here
January 11, 2012