Pattern Matching with Swaps

Let a text string T of n symbols and a pattern string P of m symbols from alphabet /spl Sigma/ be given. A swapped version T' of T is a length n string derived from T by a series of local swaps, (i. e. t/sup '//sub l//spl larr/t/sub l+1/ and t'/sub l+1//spl larr/t/sub 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 where there is 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(mn) time. In this paper we show the first algorithm that solves the pattern matching with swaps problem in time O(mn). We present an algorithm whose time complexity is O(nm/sup 1/3/ log m log/sup 2/ /spl sigma/) for a general alphabet /spl Sigma/, where /spl sigma/=min(m, |/spl Sigma/|).

Authors

• Amihood Amir
• Yonatan Aumann
• Gad M. Landau
• Moshe Lewenstein
• Noa Lewenstein

Keywords

• Pattern matching
• Computer science
• Mathematics
• Art
• Tellurium
• Dynamic programming
• Heuristic algorithms
• DNA
• Software libraries
• Discrete Fourier transforms
• Time Complexity
• Problem In Time
• Binary String
• Permutation
• Convolution
• Search String
• Substring
• Matching Problem
• Induction Hypothesis
• Stream Length
• Stream Types