Jumbled indexing is the problem of indexing a text T for queries that ask whether there is a
substring of T matching a pattern represented as a Parikh vector, ie, the vector of frequency …

Text indexing, the problem in which one desires to preprocess a (usually large) text for future
(shorter) queries, has been researched ever since the suffix tree was invented in the early …

A 1-prefix normal word is a binary word with the property that no factor has more 1s than the
prefix of the same length; a 0-prefix normal word is defined analogously. These words arise …

We consider the problem of answering shortest unique substring (SUS) queries on run-
length encoded strings. For a string S, a unique substring u= S [i.. j] is said to be a shortest …

In this paper we investigate jumbled (Abelian) versions of three classical strings problems. In
all these problems we assume the input string S [1.. n] is given in its run-length format S′[1 …

Given a sequence of n numbers, the MAXIMUM CONSECUTIVE SUBSUMS PROBLEM
(MCSP) asks for the maximum consecutive sum of lengths ℓ for each ℓ= 1,…, n. No algorithm …

A prefix normal word is a binary word with the property that no substring has more 1s than
the prefix of the same length. This class of words is important in the context of binary jumbled …

Binary jumbled pattern matching asks to preprocess a binary string SS in order to answer
queries (i, j)(i, j) which ask for a substring of SS that is of length ii and has exactly jj 1-bits …

We present efficient algorithms computing all Abelian periods of two types in a word.
Regular Abelian periods are computed in O (n log log {n}) randomized time which improves …

We consider how to index strings, trees and graphs for jumbled pattern matching when we
are asked to return a match if one exists. For example, we show how, given a tree containing …