We present a collection of new results on problems related to 3SUM, including: The first truly
subquadratic algorithm for computing the (min,+) convolution for monotone increasing …

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 …

Given a string s, the Parikh vector of s, denoted p (s), counts the multiplicity of each character
in s. Searching for a match of a Parikh vector q in the text s requires finding a substring t of s …

We introduce efficient data structures for an indexing problem in non-standard stringology—
jumbled pattern matching. Moosa and Rahman J. Discr. Alg., 2012 gave an index for …

In recent years much effort was put into developing polynomial-time conditional lower
bounds for algorithms and data structures in both static and dynamic settings. Along these …

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 present a new class of binary words: the prefix normal words. They are defined by the
property that for any given length k, no factor of length k has more a's than the prefix of the …

The Binary Jumbled String Matching Problem is defined as follows: Given a string s over {a,
b} of length n and a query (x, y), with x, y non-negative integers, decide whether s has a …

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 …