10.1007/s00224-011-9344-5 Burcsi, Peter Peter Burcsi Cicalese, Ferdinando Ferdinando Cicalese Fici, Gabriele Gabriele Fici Lipták, Zsuzsanna Zsuzsanna Lipták On Approximate Jumbled Pattern Matching in Strings Springer Science + Business Media 2012 2012-03-01T09:55:25Z 2018-07-24T13:00:40Z journal_article https://pub.uni-bielefeld.de/record/2474531 https://pub.uni-bielefeld.de/record/2474531.json 1432-4350 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.