Indexed Swap Matching for Short Patterns

スポンサーリンク

概要

• 論文の詳細を見る

• 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(λmlog 2n) on an O(nHk) bits indexing data structure. Here λ is a constant. Our solution is more effective when the pattern is short.

• 2012-01-01

著者

• Lu Songfeng

  School Of Computer Science Huazhong University Of Science And Technology

• Zhao Hua

  School Of Computer Science Huazhong University Of Science And Technology

関連論文

• An Empirical Study on the Contribution of Land to the Economic Growth in the Chinas Yangtze River Delta
• Indexed Swap Matching for Short Patterns
• Synthesis of Large-area Vertically Aligned Silicon Nanotip Arrays by Combining Silver Mirror Reaction with Metal-catalyzed Electroless Etching

スポンサーリンク