Algorithms and Indexing Lower Bounds for Variable String Matching

Estéban Gabory

A \emph{generalized degenerate string} (GD) is a sequence $T=T_1\dots T_n$ of nonempty finite sets of strings, called \emph{segments}, such that all strings in a segment have the s…