
handle: 20.500.11769/76669
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 $\mathcal{O}(nm^2)$ general algorithm, named Backward-Cross-Sampling, and show an efficient implementation of it, based on bit-parallelism, which achieves $\mathcal{O}(nm)$ worst-case time and $\mathcal{O}(\sigma)$-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.
Combinatorial algorithms on words; Design and analysis of algorithms; Nonstandard pattern matching; Pattern matching with swaps
Combinatorial algorithms on words; Design and analysis of algorithms; Nonstandard pattern matching; Pattern matching with swaps
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
