MATCHING A SET OF STRINGS WITH VARIABLE-LENGTH DONT CARES

Given an alphabet A, a pattern p is a word v(1)@...@v(m), where v(i) e psilon A and @ is not an element of A is a distinguished symbol calle d a variable length don't care symbol. Pattern p matches a text t epsi lon A if t = u(O)v(1)u(l)...u(m-1)v(m)u(m) for some u(O),..., u(m) ep silon A. We address the following problem: given a set P of patterns and a text t, test whether one of the patterns of P matches t. We desc ribe an algorithm that serves the problem in time O((\t\+\P\)log\P\). In contrast to most of the existing string matching algorithms (such a s that of Aho-Corasick) our algorithm is not composed of two successiv e stages - preprocessing the pattern (resp. the text) and reading thro ugh the text (reap. the pattern) - but has these two stages essentiall y interleaved. Our approach is based on using the DAWG (Directed Acycl ic Word Graph), a data structure studied by A. Blumer J. Blumer, Hauss ler, Ehrenfeucht, Crochemore, Chen, Seiferas.