Efficient indexing algorithms for one-dimensional discretely-scaled strings

The discretely-scaled string indexing problem asks one to preprocess a given text string T, so that for a queried pattern P, the matched positions in T that P appears with some discrete scale can be reported efficiently. For solving this problem, Wang et al. first show that with an O(|T|log|T|)-time preprocessing on T, all matched positions can be reported in O(|P|+Ud) time, where |T|, |P|, and Ud denote the length of T, the length of P, and the number of matched positions for discretely-scaled P in T, respectively. In this paper, for fixed alphabets we propose the first-known optimal indexing algorithm that takes O(|T|) and O(|P|+Ud) time in its preprocessing and query phases, respectively. For integer and unbounded alphabets, our new algorithm can also be extended to obtain the best-known results.