A new algorithm for efficient pattern matching with swaps
International Workshop on Combinatorial Algorithms, 2009•Springer
Abstract The Pattern Matching problem with Swaps consists in finding all occurrences of a
pattern P in a text T, when disjoint local swaps in the pattern are allowed. In this paper, we
present a new efficient algorithm for the Swap Matching problem with short patterns. In
particular, we devise a O(nm^2) general algorithm, named Backward-Cross-Sampling, and
show an efficient implementation of it, based on bit-parallelism, which achieves O(nm) worst-
case time and O(σ)-space complexity, with patterns whose length m is comparable to the …
pattern P in a text T, when disjoint local swaps in the pattern are allowed. In this paper, we
present a new efficient algorithm for the Swap Matching problem with short patterns. In
particular, we devise a O(nm^2) general algorithm, named Backward-Cross-Sampling, and
show an efficient implementation of it, based on bit-parallelism, which achieves O(nm) worst-
case time and O(σ)-space complexity, with patterns whose length m is comparable to the …
Abstract
The Pattern Matching problem with Swaps consists in finding all occurrences of a pattern P in a text T, when disjoint local swaps in the pattern are allowed.
In this paper, we present a new efficient algorithm for the Swap Matching problem with short patterns. In particular, we devise a general algorithm, named Backward-Cross-Sampling, and show an efficient implementation of it, based on bit-parallelism, which achieves worst-case time and -space complexity, with patterns whose length m is comparable to the word-size of the target machine (n and σ are respectively the size of the text and of the alphabet).
From an extensive comparison with some of the most recent and effective algorithms for the swap matching problem, it turns out that our algorithm is very flexible and achieves very good results in practice.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果