Finite State Methods for String Matching

Abstract:

I review some recent contributions to methods based on finite automata for the String Matching problem and for some of its variants. In particular, I shall present a novel technique, suitable for bit-parallelism, to represent both the nondeterministic automaton and the nondeterministic suffix automaton of a given string in a more compact way. This new approach is based on a particular factorization of strings which, on the average, allows to reduce the size of the bit-vectors needed to encode the automaton. If one restricts to a single machine word of w bits, this method makes it possible to encode automata of strings longer than w.

This talk is part of a series of meetings for string algorithms researchers in the Helsinki area.