String matching with inversions and translocations in linear average time (most of the time)

We present an efficient algorithm for finding all approximate occurrences of a given pattern p of length m in a text t of length n allowing for translocations of equal length adjacent factors and inversions of factors. The algorithm is based on an efficient filtering method and has an O(nm max(alpha, beta))-time complexity in the worst case and O(max(alpha, beta, sigma))-space complexity, where alpha and beta are respectively the maximum length of the factors involved in any translocation and inversion, and a is the alphabet size. Moreover we show that our algorithm has an O(n) average time complexity, whenever sigma = Omega(log m/log log(1-epsilon) m), for epsilon > 0. Experiments show that the proposed algorithm achieves very good results in practical cases. (C) 2011 Elsevier B.V. All rights reserved.