On Approximate Jumbled Pattern Matching in Strings

Burcsi P, Cicalese F, Fici G, Lipták Z (2012)
Theory of Computing Systems 50(1): 35-51.

Journal Article | Published | English

No fulltext has been uploaded

Author
; ; ;
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.
Publishing Year
ISSN
eISSN
PUB-ID

Cite this

Burcsi P, Cicalese F, Fici G, Lipták Z. On Approximate Jumbled Pattern Matching in Strings. Theory of Computing Systems. 2012;50(1):35-51.
Burcsi, P., Cicalese, F., Fici, G., & Lipták, Z. (2012). On Approximate Jumbled Pattern Matching in Strings. Theory of Computing Systems, 50(1), 35-51.
Burcsi, P., Cicalese, F., Fici, G., and Lipták, Z. (2012). On Approximate Jumbled Pattern Matching in Strings. Theory of Computing Systems 50, 35-51.
Burcsi, P., et al., 2012. On Approximate Jumbled Pattern Matching in Strings. Theory of Computing Systems, 50(1), p 35-51.
P. Burcsi, et al., “On Approximate Jumbled Pattern Matching in Strings”, Theory of Computing Systems, vol. 50, 2012, pp. 35-51.
Burcsi, P., Cicalese, F., Fici, G., Lipták, Z.: On Approximate Jumbled Pattern Matching in Strings. Theory of Computing Systems. 50, 35-51 (2012).
Burcsi, Peter, Cicalese, Ferdinando, Fici, Gabriele, and Lipták, Zsuzsanna. “On Approximate Jumbled Pattern Matching in Strings”. Theory of Computing Systems 50.1 (2012): 35-51.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar