String matching under a general matching relation

S. Muthukrishnan, H. Ramesh

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

    Abstract

    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 text positions are sought at which the pattern matches under this relation. Depending upon the existence of a simple, easily recognizable property in the given matching relation, we show that string matching either requires time linear in the text and pattern lengths or is at least as hard as boolean multiplication. Since the existence of a linear time algorithm for boolean multiplication has been a long-standing open question, designing linear time algorithms for matching relations in the latter category appears to be hard. 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 initiate the study of a generic string matching algorithm that works for any matching relation. We give an algorithm that given any matching relation, pattern and text runs in O(n(sm)1/3 polylog(m)), where n and m are the sizes of the text and the pattern respectively, and s is a factor related to the size of the given matching relation. This complexity is o(nm) except for very dense matching relations.

    Original languageEnglish (US)
    Title of host publicationFoundations of Software Technology and Theoretical Computer Science - 12th Conference, Proceedings
    EditorsRudrapatna Shyamasundar
    PublisherSpringer Verlag
    Pages356-367
    Number of pages12
    ISBN (Print)9783540562870
    DOIs
    StatePublished - 1992
    Event12th Conference on Foundations of Software Technology and Theoretical Computer Science, 1992 - New Delhi, India
    Duration: Dec 18 1992Dec 20 1992

    Publication series

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

    Conference

    Conference12th Conference on Foundations of Software Technology and Theoretical Computer Science, 1992
    CountryIndia
    CityNew Delhi
    Period12/18/9212/20/92

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

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

  • Cite this

    Muthukrishnan, S., & Ramesh, H. (1992). String matching under a general matching relation. In R. Shyamasundar (Ed.), Foundations of Software Technology and Theoretical Computer Science - 12th Conference, Proceedings (pp. 356-367). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 652 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-56287-7_118