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 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 present a new approach for solving both the Swap Matching problem and the Approximate Swap Matching problem in linear time, in the case of short patterns. In particular, we devise a O(nm) general algorithm, named Cross-Sampling, and show an efficient implementation of it, based on bit-parallelism, which achieves O(n) worst-case time and O(s)-space complexity, with patterns whose length is comparable to the word-size of the target machine.
Pattern matching with swaps for short patterns in linear time
CANTONE, Domenico;FARO, SIMONE
2009-01-01
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 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 present a new approach for solving both the Swap Matching problem and the Approximate Swap Matching problem in linear time, in the case of short patterns. In particular, we devise a O(nm) general algorithm, named Cross-Sampling, and show an efficient implementation of it, based on bit-parallelism, which achieves O(n) worst-case time and O(s)-space complexity, with patterns whose length is comparable to the word-size of the target machine.File | Dimensione | Formato | |
---|---|---|---|
2009 CantoneFaro SOFSEM.pdf
solo gestori archivio
Tipologia:
Versione Editoriale (PDF)
Dimensione
248 kB
Formato
Adobe PDF
|
248 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.