Prague Stringology Conference 2014
Domenico Cantone and Simone Faro
Efficient Online Abelian Pattern Matching in Strings by Simulating Reactive Multi-Automata
| Abstract: |
| The abelian pattern matching problem consists in finding all substrings of a text which are permutations of a given pattern. This problem finds application in many areas and can be solved in linear time by a naïve sliding window approach. In this paper we introduce a new approach to the problem which makes use of a reactive multi-automaton modeled after the pattern, and provides an efficient nonstandard simulation of the automaton based on bit-parallelism. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |