Two-dimensional dictionary matching

Amihood Amir, Martin Farach

    Research output: Contribution to journalArticlepeer-review


    Most traditional pattern matching algorithms solve the problem of finding all occurrences of a given pattern string P in a given text T. Another important paradigm is the dictionary matching problem. Let D={P1,...,Pk} be the dictionary. We seek the locations of all dictionary patterns that appear in a given text T. Previous dictionary matching algorithms have all involved exact matching of a set of strings. In this paper, we present an algorithm for the Two-Dimensional Dictionary Problem. The two-dimensional dictionary problem is that of finding each occurrence of a set of two-dimensional patterns in a text. Our algorithm runs in time O(|D|log k) preprocessing, O(|T|log k) text processing.

    Original languageEnglish (US)
    Pages (from-to)233-239
    Number of pages7
    JournalInformation Processing Letters
    Issue number5
    StatePublished - Dec 21 1992


    • Algorithms
    • analysis of algorithms
    • dictionary matching
    • pattern matching
    • text processing

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Signal Processing
    • Information Systems
    • Computer Science Applications


    Dive into the research topics of 'Two-dimensional dictionary matching'. Together they form a unique fingerprint.

    Cite this