For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Indexed Swap Matching for Short Patterns
Hua ZHAO Songfeng LU
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2012/01/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
algorithms, pattern matching, pattern matching with swaps, suffix array, compressed suffix array,
Full Text: PDF(242.6KB)
>>Buy this Article
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 O(λmlog2 n) on an O(nHk) bits indexing data structure. Here λ is a constant. Our solution is more effective when the pattern is short.