Pattern matching with swaps

Let a text string T of n symbols and a pattern string P of m symbols from a lphabet Sigma be given. A swapped version T' of T is a length n string deri ved from T by a series of local swaps (i.e., t(l)' <-- t(l+1) and t(l+1)' < -- t(l)), where each element can participate in no more than one swap. The pattern matching with swaps problem is that of finding all locations i for which there exists a swapped version T' of T with an exact matching of P in location i of T'. It has been an open problem whether swapped matching can be done in less than O(nm) time. In this paper we show the first algorithm that solves the pattern matching with swaps problem in time o(nm). We pres ent an algorithm whose time complexity is O(nm(1/3) log m log sigma) for a general alphabet Sigma, where sigma = min(m, \Sigma\). (C) 2000 Academic Pr ess.