Generalized String Matching

Philippe Jacquet, Wojciech SzpankowskiCambridge 2015 · DOI · OpenAlex

Abstract

In this chapter we consider generalized pattern matching, in which a set of patterns (rather than a single pattern) is given. We assume here that the pattern is a pair of sets of words (W0, W), where Wi consists of the sets Wi ⊂ Ami (i.e., all words in Wi have a fixed length mi). The set W0 is called the forbidden set. For W0 = ∅ one is interested in the number of pattern occurrences On(W), defined as the number of patterns from W occurring in a text generated by a (random) source. Another parameter of interest is the number of positions in where a pattern from W appears (clearly, several patterns may occur at the same positions but words from Wi must occur in different locations); this quantity we denote as Πn. If we define as the number of positions where a word from Wi occurs, then
BibTeX
@inproceedings{jacquet2015generalized,
  author = {Philippe Jacquet and Wojciech Szpankowski},
  title = {{Generalized String Matching}},
  booktitle = {Cambridge},
  year = {2015},
  doi = {10.1017/cbo9780511843204.007},
}

Loading related content...

Figure