The Prague Stringology Conference 2005

Jan Antoš and Bořivoj Melichar

Backward Pattern Matching Automaton

We present a new algorithm to solve a large number of backward pattern matching problems. This algorithm is specified by the theory of finite automata. The algorithm is based on the utilization of a formal tool called "Backward Pattern Matching Automaton", which we specify in this paper. Introduction of such a tool presents a formal base to the world of backward pattern matching.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF