Approximate string matching using compressed suffix arrays

Abstract

Let T be a text of length n and P be a pattern of length m, both strings over a fixed finite alphabet A. The k-difference (k-mismatch, respectively) problem is to find all occurrences of P in T that have edit distance (Hamming distance, respectively) at most k from P. In this paper we investigate a well-studied case in which k = 1 and T is fixed and preprocessed into an indexing data structure so that any pattern query can be answered faster [16-19]. This paper gives a solution using O(n) bits indexing data structure with O(m log 2 n) query time. To the best of our knowledge, this is the first result which requires linear indexing space. The results can be extended for the fc-difference problem with k ≥ 1. © Springer-Verlag 2004.