String matching under a general matching relation

S. Muthukrishnan, H. Ramesh

    Research output: Contribution to journalArticlepeer-review


    In standard string matching, each symbol matches only itself, In other string matching problems, e.g., the string matching with “don’t-cares” problem, a symbol may match several symbols. In general, an arbitrary many-to-many matching relation might hold between symbols. We consider a general string matching problem in which such a matching relation is specified and those positions in a text t, of length n, are sought at which the pattern p, of length m, matches under this relation. Depending upon the existence of a simple and easily recognizable property in the given matching relation, we show that string matching either requires linear (i.e., O(n + m)) time or is at least as hard as boolean convolution. As an application, we show that the matching relations of several independently studied string matching problems do indeed fall into the latter (hard) category. We also give a generic string matching algorithm that works far any matching relation and has complexity o(nm) except for very “large” matching relations.

    Original languageEnglish (US)
    Pages (from-to)140-148
    Number of pages9
    JournalInformation and Computation
    Issue number1
    StatePublished - Oct 1995

    ASJC Scopus subject areas

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


    Dive into the research topics of 'String matching under a general matching relation'. Together they form a unique fingerprint.

    Cite this