Approximate String Matching Allowing for Inversions and Translocations.
Domenico Cantone, Simone Faro, Emanuele Giaquinta · 2010
Abstract. The approximate string matching problem consists in finding all locations at which a pattern P of length m matches a substring of a text T of length n, after a given finite number of edit operations. In this paper we investigate such problem when the string distance involves transloca-tions of equal length adjacent factors and inversions of factors. In particular, we devise a O(nmmax(α, β))-time and O(m2)-space algorithm, where α and β are respectively the maximum length of the factors involved in any translocation and inversion. Our algo-rithm is based on the dynamic-programming approach and makes use of the Directed Acyclic Word Graph of the pattern. Moreover we show that under the assumptions of equiprobability and independence of characters our algorithm has a O(n logσ m) average time complexity. Finally, we briefly sketch in an appendix an efficient imple-mentation, based on bit-parallelism. 1