Matching a set of strings with variable length don't cares

AbstractGiven an alphabet A, a pattern p is a word ν1@…@νm, where νi ϵ A∗ and @ ϵ̷ A is a distinguished symbol called a variable length don't care symbol. Pattern p matches a text t ϵ A∗ if t = u0ν1u1…um − 1νmum for some u0,…,um ϵ 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 describe an algorithm that solves the problem in time O((¦t¦ + ¦P¦)log¦P¦).In contrast to most of the existing string matching algorithms (such as that of Aho-Corasick) our algorithm is not composed of two successive stages — preprocessing the pattern (resp. the text) and reading through the text (resp. the pattern) — but has these two stages essentially interleaved. Our approach is based on using the DAWG (Directed Acyclic Word Graph), a data structure studied by A. Blumer J. Blumer, Haussler, Ehrenfeucht, Crochemore, Chen, seiferas