Efficient randomized dictionary matching algorithms

Amihood Amir, Martin Farach, Yossi Matias

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    The standard string matching problem involves finding all occurrences of a single pattern in a single text. While this approach works well in many application areas, there are some domains in which it is more appropriate to deal with dictionaries of patterns. A dictionary is a set of patterns; the goal of dictionary matching is to find all dictionary patterns in a given text, simultaneously. In string matching, randomized algorithms have primarily made use of randomized hashing functions which convert strings into “signatures” or “finger prints”. We explore the use of finger prints in conjunction with other randomized and deterministic techniques and data structures. We present several new algorithms for dictionary matching, along with parallel algorithms which are simpler of more efficient than previously known algorithms.

    Original languageEnglish (US)
    Title of host publicationCombinatorial Pattern Matching - 3rd Annual Symposium, Proceedings
    EditorsAlberto Apostolico, Maxime Crochemore, Zvi Galil, Zvi Galil, Udi Manber
    PublisherSpringer Verlag
    Number of pages14
    ISBN (Print)9783540560241
    StatePublished - 1992
    Event3rd Annual Symposium on Combinatorial Pattern Matching, 1992 - Tucson, United States
    Duration: Apr 29 1992May 1 1992

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume644 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other3rd Annual Symposium on Combinatorial Pattern Matching, 1992
    Country/TerritoryUnited States

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Efficient randomized dictionary matching algorithms'. Together they form a unique fingerprint.

    Cite this