Algorithms for Jumbled Indexing, Jumbled Border and Jumbled Square on run-length encoded strings

In this paper we investigate jumbled (Abelian) versions of three classical strings problems. In all these problems we assume the input string is given in its run-length format .The is the problem of indexing a string over for histogram queries, i.e. given a pattern , we want to find all substrings of that are permutations of . We provide an algorithm that constructs an index of size in time , which allows answering histogram queries in -time.The is the problem of finding for every location in , the longest proper prefix of that is also a permutation of a proper suffix of , if such exists. We provide an algorithm that solves this problem in time, and space.A is a string of the form , where is a permutation of . The is the problem of finding for every location in , the longest jumbled square that ends in , if such exists. We provide an algorithm that solves this problem in time, and space.