Monotonic run length text sampling and fake sampled positions

Abstract Text-sampling is an efficient approach for string matching problems introduced in order to overcome the prohibitive space requirements of indexed matching, on the one hand, and drastically reduce searching time for the online solutions, on the other hand. Known solutions to sampled string matching are very efficient in practical cases being able to improve standard online string matching algorithms up to $99.6$% using in the best cases $<1$% of the original text size when applied to natural languages combined with the condensed alphabet. In this paper we present our results obtained in an attempt to extend sampled-string matching to the general case of nonclassical string matching. Specifically, we introduce a new sampling approach that turns out to be suitable for both exact and nonclassical matching and evaluate it in the context of two specific cases of nonclassical matching, the order-preserving pattern matching problem and the Cartesian tree pattern matching problem. Our experimental results show that the new approach is extremely competitive both in terms of space and running time, and for both classical and nonclassical matching. We also discuss the applicability of the new approach to other different nonclassical string matching problems.