In the dynamic dictionary matching problem, a dictionary D contains a
set of patterns that can change over time by insertion and deletion of
individual patterns. The user also presents text strings and asks for
all occurrences of any patterns in the text. The two main contributio
ns of this paper are: (1) a faster algorithm for dynamic string dictio
nary matching with bounded alphabets, and (2) a dynamic dictionary mat
ching algorithm for two-dimensional texts and patterns. The first cont
ribution is based on an algorithm that solves the general problem of m
aintaining a sequence of well-balanced parentheses under the operation
s insert, delete, and find nearest enclosing parenthesis pair. The mai
n new idea behind the second contribution is a novel method to efficie
ntly manipulate failure links for two-dimensional patterns. (C) 1995 A
cademic Press. Inc.