Algorithms for Jumbled Indexing, Jumbled Border and Jumbled Square on Run-Length Encoded Strings

Jumbled Indexing, the problem of indexing a text for histogram queries, has been of much interest lately. In this paper we consider jumbled indexing for run-length encoded texts. We refute a former conjecture and show an algorithm for general sized alphabets. We also consider Jumbled Borders, the extension of borders to jumbled strings. Borders are the basis for various algorithms. Finally, we consider Jumbled Squares, strings which are of the form $x\bar{x}$ , where $\bar{x}$ is a jumbling of x. We show efficient algorithms for these problems.