@article{2474531,
abstract = {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 with p(t) = q. This can be viewed as the task of finding a jumbled (permuted) version of a query pattern, hence the term Jumbled Pattern Matching. We present several algorithms for the approximate version of the problem: Given a string s and two Parikh vectors u, v (the query bounds), find all maximal occurrences in s of some Parikh vector q such that u <= q <= v. This definition encompasses several natural versions of approximate Parikh vector search. We present an algorithm solving this problem in sub-linear expected time using a wavelet tree of s, which can be computed in time O(n) in a preprocessing phase. We then discuss a Scrabble-like variation of the problem, in which a weight function on the letters of s is given and one has to find all occurrences in s of a substring t with maximum weight having Parikh vector p(t) <= v. For the case of a binary alphabet, we present an algorithm which solves the decision version of the Approximate Jumbled Pattern Matching problem in constant time, by indexing the string in subquadratic time.},
author = {Burcsi, Peter and Cicalese, Ferdinando and Fici, Gabriele and Lipták, Zsuzsanna},
issn = {1433-0490},
journal = {Theory of Computing Systems},
number = {1},
pages = {35--51},
publisher = {Springer Science + Business Media},
title = {{On Approximate Jumbled Pattern Matching in Strings}},
doi = {10.1007/s00224-011-9344-5},
volume = {50},
year = {2012},
}