Indexed Swap Matching for Short Patterns

Hua ZHAO  Songfeng LU  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E95-A   No.1   pp.362-366
Publication Date: 2012/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E95.A.362
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Keyword: 
algorithms,  pattern matching,  pattern matching with swaps,  suffix array,  compressed suffix array,  

Full Text: PDF(242.6KB)
>>Buy this Article


Summary: 
Let T be a text of length n and P be a pattern of length m, both strings over a fixed finite alphabet. The Pattern Matching with Swaps problem is to find all occurrences of P in T if adjacent pattern characters can be swapped. In the Approximate Pattern Matching problem with Swaps, one seeks for every text location with a swapped match of P, the number of swaps necessary to obtain a match at the location. In this paper we provide the first off-line solution for the swap matching problem and the approximate pattern matching problem with swaps. We present a new data-structure called a Swap-transforming Tree. And we give a precise upper-bond of the number of the swapped versions of a pattern. By using the swap-transforming tree, we can solve both problems in time Omlog2 n) on an O(nHk) bits indexing data structure. Here λ is a constant. Our solution is more effective when the pattern is short.