In recent years, significant progress has been made in explaining the apparent hardness of
improving upon the naive solutions for many fundamental polynomially solvable problems …

The study of the effect that errors may have on computation started at the very beginning of
the history of computer science. It dates back to the early 1950s, to the research by von …

We introduce a new metric of match, called Cartesian tree matching, which means that two
strings match if they have the same Cartesian trees. Based on Cartesian tree matching, we …

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 …

We introduce a new metric of match, called Cartesian tree matching, which means that two
strings match if they have the same Cartesian trees. Based on Cartesian tree matching, we …

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 …

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 …

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 …