Improved string matching with k mismatches
Zvi Galil, Raffaele Giancarlo · ACM SIGACT News · 1986
Given a text string t0 t1 . . .tn_1 , a pattern string p0 p1 • • .pm-1and an integer k, k m 5 n, we are interested i n finding all occurrences of the pattern in the text with at most k mismatches, i .e. with at most k location s in which the pattern and the text have different symbols .Recently, an efficient algorithm for such a problem has been devised by [2] .Its time performance i s 0(k(mlogm+n)) and it uses 0(k(m+n)) space.Here we present a compact version of their algorithm , achieving a time performance of 0(mlogm+kn) for general alphabets and of 0(m+kn) for alphabet s whose size is fixed .Our algorithm uses 0(m) space.The data structure that we use is the suffix tree [1] o f the pattern modified in order to support the static lowest common ancestor algorithm (LCA for short) given in [5] .In more recent versions of [2] the authors used the suffix tree for the problem of strin g matching with k differences [4] but not for the problem of string matching with k mismatches [3] .The suffix tree T of the string p0p1 . ..pm-1 is a digital search tree of 0(m) nodes containing all suffixes o f that string .Each leaf of T is labeled with a distinct integer j so that the path from the root of T to lea f (labeled) j corresponds to suffix pjpj+1 •• •pm-1 • A fast algorithm for the construction of T is reported in [1 ] and it takes 0(mlogm) time for general alphabet .When the alphabet has a fixed size, it takes 0(m) .The LCA algorithm is used to quickly find the length of the longest common prefix between suffixes p i. ..p m_1 and Indeed, we assume that the query LCA(T,i j) returns such a length .We recall that the LCA algorithm is linear in the number of queries [5] .The algorithm can be informally described as follows .The algorithm tests, in increasing order, all positions of the text in order to locate occurrences of the pattern in the text with at most k mismatches .Let inew be the current position to be tested and le t