Enabling FM-Index for Elastic-Degenerate Strings via a New Min/Max Wavelet Tree

Elastic-degenerate (ED) strings generalize classic strings by allowing each position to store a set of up to h strings of arbitrary lengths [2]. An ED string is a restricted version of a regular expression whose expressiveness still causes a combinatorial explosion of possible resolutions (i.e., the members of its language), making classical pattern matching and indexing techniques either inefficient or inapplicable. A position in an ED string is called solid if it stores a single symbol, otherwise elastic. We introduce the Min/Max wavelet tree (MM-WT), a variant of the wavelet tree supporting semantics-aware rank and select on ED strings. Each leaf stores two arrays per symbol c, c and M c, giving for each position the minimum and maximum symbol count across all alternatives. Prefix sums bound the number of occurrences in any resolution of a prefix, so sm-rank (c, i) returns an interval [r, rM] of possible ranks, and sm-select (c, j) returns an interval for the j-th occurrence of c. On classic strings, min and max collapse to the same counts and the structure becomes a standard wavelet tree. The structure uses the same space as a subset wavelet tree [1] internally, plus O(n σ h) bits for the min/max arrays, and supports both queries in O( σ) time.