Generalized String Matching
Lists
Only you see this
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...