New results and open problems related to non-standard stringology

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.