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

Abstract. 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 allow-ing for translocations of equal length adjacent factors and inversions of factors. The algorithm is based on an efficient filtering method and has an O(nmmax(α, β))-time complexity in the worst case and O(max(α, β))-space complexity, where α and β are respectively the maximum length of the factors involved in any translocation and inversion. Moreover we show that under the assumptions of equiprobability and independence of characters our algorithm has a O(n) average time complexity, whenever σ = Ω(logm / log log1−εm), where ε> 0 and σ is the dimension of the alphabet. Experiments show that the new proposed algorithm achieves very good results in practical cases.