Improved dynamic dictionary matching

Amihood Amir, Martin Farach, Ramana M. Idury, Johannes A. Lapoutre, Alejandro A. Schaffer

    Research output: Contribution to journalArticlepeer-review


    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 contributions of this paper are: (1) a faster algorithm for dynamic string dictionary matching with bounded alphabets, and (2) a dynamic dictionary matching algorithm for two-dimensional texts and patterns. The first contribution is based on an algorithm that solves the general problem of maintaining a sequence of well-balanced parentheses under the operations insert, delete, and find nearest enclosing parenthesis pair. The main new idea behind the second contribution is a novel method to efficiently manipulate failure links for two-dimensional patterns.

    Original languageEnglish (US)
    Pages (from-to)258-282
    Number of pages25
    JournalInformation and Computation
    Issue number2
    StatePublished - Jun 1995

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Information Systems
    • Computer Science Applications
    • Computational Theory and Mathematics


    Dive into the research topics of 'Improved dynamic dictionary matching'. Together they form a unique fingerprint.

    Cite this