New results and open problems related to non-standard stringology

S. Muthukrishnan

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


    There are a number of string matching problems for which the best known algorithms rely on algebraic convolutions (an approach pioneered by Fischer and Paterson [FP74]). These include for instance the classical string matching with wild cards and the k-mismatches problem. In IMP94], the authors studied generalizations of these problems which they called the non-standard stringology. There they derived upper and lower bounds for non-standard string matching problems. In this paper, we pose several novel problems in the area of nonstandard stringology. Some we have been able to resolve here; others we leave open. Among the technical results in this paper are: 1. improved bounds for string matching when a symbol in the string matches at most d others (motivated by noisy string matching), 2. first-known bounds for approximately counting mismatches in noisy string matching as above, and 3. improved bounds for the k-witnesses problem and its applications. Our results are obtained by using the probabilistic proof technique and randomized algorithmic methods; these techniques, although standard, have seldom been used in combinatorial pattern matching.

    Original languageEnglish (US)
    Title of host publicationCombinatorial Pattern Matching - 6th Annual Symposium, CPM 1995, Proceedings
    EditorsZvi Galil, Esko Ukkonen
    PublisherSpringer Verlag
    Number of pages20
    ISBN (Print)3540600442, 9783540600442
    StatePublished - 1995
    Event6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995 - Espoo, Finland
    Duration: Jul 5 1995Jul 7 1995

    Publication series

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


    Other6th Annual Symposium on Combinatorial Pattern Matching, CPM 1995

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'New results and open problems related to non-standard stringology'. Together they form a unique fingerprint.

    Cite this