DYNAMIC DICTIONARY MATCHING IN EXTERNAL MEMORY

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.