Prague Stringology Conference 2014

Domenico Cantone and Simone Faro

Efficient Online Abelian Pattern Matching in Strings by Simulating Reactive Multi-Automata

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: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation