The Prague Stringology Conference 2005

Jan Lahoda and Bořivoj Melichar

General Pattern Matching on Regular Collage System

This paper presents a brand new approach to the general pattern matching on regular collage systems. Our approach provides O(||D||+|S|+E) (where E is the preprocessing cost) worst-case time complexity. It is based on fact that a deterministic finite automaton is able to distinguish only a limited number of strings.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF