In the dynamic dictionary matching problem, a dictionary D contains a
set of patterns that can change over time under insertion and deletion
of individual patterns. Given an arbitrary text T, we must efficientl
y list all the dictionary patterns that occur at each text position. W
e investigate the I/O complexity of this problem for a large dictionar
y that must be stored in external storage devices. By following a comp
letely new approach, we devise an efficient solution which is based up
on the SE-tree data structure (P. Ferragina and R. Grossi, 1995, in ''
Proc. ACM Symposium on Theory of Computing,'' pp. 693-702), and a nove
l notion of certificate for the dictionary matching problem. Our data
structure can be adapted to efficiently work in main memory and to sol
ve other problems, thus providing a new insight into the nature of the
dictionary matching problem. (C) 1998 Academic Press.