IMPROVED DYNAMIC DICTIONARY MATCHING

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.