Approximate string-matching with q-grams and maximal matches

AbstractWe 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 q-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 O(n log (m–q)). The occurrences with distance ⩽k can be found in time O(n log k). The other distance function is based on finding maximal common substrings and allows a form of approximate string-matching in time O(n). Both distances give a lower bound for the edit distance (in the unit cost model), which leads to fast hybrid algorithms for the edit distance based string-matching