Click a term to initiate a search.
Ukkonen, E., Approximate string-matching with ¿/-grams and maximal matches. Theoretical Com-
puter Science 92 (1992) 191-211.
We study approximate string-matching in connection with two string distance functions that are
computable in linear time. The first function is based on the so-called ij-grams. An algorithm is given
for the associated string-matching problem that finds the locally best approximate occurrences of
pattern P, |P| = m, in text T, \T\ = n, in time 0(«log(m — q)). The occurrences with distance