Alphabet independent approach to two-dimensional pattern matching

Amihood Amir, Gary Benson, Martin Farach

    Research output: Contribution to journalArticlepeer-review


    The authors show an algorithm for two-dimensional matching with an O(n2log m ) text-scanning phase. Furthermore, the text scan requires no special assumptions about the alphabet, i.e. it runs on the same model as the standard linear-time string-matching algorithm. The pattern preprocessing requires an ordered alphabet and runs with the same alphabet dependency as the previously known algorithms.

    Original languageEnglish (US)
    Pages (from-to)313-323
    Number of pages11
    JournalSIAM Journal on Computing
    Issue number2
    StatePublished - 1994

    ASJC Scopus subject areas

    • General Computer Science
    • General Mathematics


    Dive into the research topics of 'Alphabet independent approach to two-dimensional pattern matching'. Together they form a unique fingerprint.

    Cite this