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 introduce a new theoretical approach to the problem based on a reactive automaton modeled after the pattern, and provide two efficient non standard simulations of the automaton, based on bit-parallelism. The first simulation can be implemented by at least 7 bitwise operations, while the second one involves only 2 bitwise operations to simulate the automaton behavior, when the input pattern satisfies particular conditions. The resulting algorithms achieve O(n) worst-case time complexity with patterns whose length is comparable to the word-size of the target machine.
Swap Matching in Strings by Simulating Reactive Automata
FARO, SIMONE
2013-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 this paper we introduce a new theoretical approach to the problem based on a reactive automaton modeled after the pattern, and provide two efficient non standard simulations of the automaton, based on bit-parallelism. The first simulation can be implemented by at least 7 bitwise operations, while the second one involves only 2 bitwise operations to simulate the automaton behavior, when the input pattern satisfies particular conditions. The resulting algorithms achieve O(n) worst-case time complexity with patterns whose length is comparable to the word-size of the target machine.File | Dimensione | Formato | |
---|---|---|---|
PSC2013_article02.pdf
solo gestori archivio
Tipologia:
Versione Editoriale (PDF)
Licenza:
Non specificato
Dimensione
229.39 kB
Formato
Adobe PDF
|
229.39 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.