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 …
G Fici, Z Lipták - Developments in Language Theory: 15th International …, 2011 - Springer
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 …
A Amir, A Apostolico, T Hirst, GM Landau… - Theoretical Computer …, 2016 - Elsevier
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 …
ES Laber, W Bardales… - 2014 IEEE International …, 2014 - ieeexplore.ieee.org
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 …