Algorithms for Jumbled Pattern Matching in Strings

Algorithms for Jumbled Pattern Matching in Strings,Computing Research Repository,Péter Burcsi,Ferdinando Cicalese,Gabriele Fici,Zsuzsanna Lipták

Algorithms for Jumbled Pattern Matching in Strings   (Citations: 1)
BibTex | RIS | RefWorks Download
The Parikh vector p(s) of a string s is defined as the vector of multiplicities of the characters. Parikh vector q occurs in s if s has a substring t with p(t)=q. We present two novel algorithms for searching for a query q in a text s. One solves the decision problem over a binary text in constant time, using a linear size index of the text. The second algorithm, for a general finite alphabet, finds all occurrences of a given Parikh vector q and has sub-linear expected time complexity; we present two variants, which both use a linear size index of the text.
Journal: Computing Research Repository - CORR , vol. abs/1102.1, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...It is worth mentioning that taking u = v = q, this implies an upper bound of O(nσ/|q|) on the expected time complexity for exact jumbled pattern matching (see below) over all instances where the query q satisfies the above-mentioned mild skewness assumption (namely, that in q the minimum component is upper bounded by some constant fraction of |q|/σ ), which constitute an improvement on the approach of [8, 9]...
    • ...In [8, 9] we showed how to employ wavelet trees to speed up the...
    • ... Eu,σ denote the expected value of the distance between R and L, following an EXPAND-update of R. In other words, if L is in position i, then we are interested in the (expected) value such that EXPAND(i, u) = i + . Notice that the probabilistic assumptions made on the string, together with the assumption of absence of matches, allow us to treat this value as independent of the position i. The following result about Eu,σ was proved in [9]...

    Péter Burcsiet al. On Approximate Jumbled Pattern Matching in Strings

Sort by: