The Prague Stringology Conference 2005

Jan Lahoda and Bořivoj Melichar

General Pattern Matching on Regular Collage System

Abstract:
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 article: Article in PostScript Article in PDF
 PostScript   PDF