Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Average Case Analysis
Decision Problem
Pattern Matching
String Matching
Text Indexing
Time Complexity
Time Use
Subscribe
Academic
Publications
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
Edit
Algorithms for Jumbled Pattern Matching in Strings
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Péter Burcsi
,
Ferdinando Cicalese
,
Gabriele Fici
,
Zsuzsanna Lipták
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 sublinear 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.
(
www.informatik.unitrier.de
)
(
adsabs.harvard.edu
)
(
arxiv.org
)
Citation Context
(1)
...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 abovementioned 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 EXPANDupdate 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 Burcsi
,
et al.
On Approximate Jumbled Pattern Matching in Strings
References
(20)
Efficient text fingerprinting via Parikh mapping
(
Citations: 21
)
Amihood Amir
,
Alberto Apostolico
,
Gad M. Landau
,
Giorgio Satta
Journal:
Journal of Discrete Algorithms  JDA
, vol. 1, no. 56, pp. 409421, 2003
The BoyerMooreGalil String Searching Strategies Revisited
(
Citations: 73
)
Alberto Apostolico
,
Raffaele Giancarlo
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 15, no. 1, pp. 98105, 1986
Composition Alignment
(
Citations: 5
)
Gary Benson
Conference:
Algorithms in Bioinformatics  WABI
, pp. 447461, 2003
Sequencing from Compomers: Using Mass Spectrometry for DNA DeNovo Sequencing of 200+ nt
(
Citations: 17
)
Sebastian Böcker
Conference:
Algorithms in Bioinformatics  WABI
, pp. 476497, 2003
Simulating multiplexed SNP discovery rates using basespecific cleavage and mass spectrometry
(
Citations: 6
)
Sebastian Böcker
Journal:
Bioinformatics/computer Applications in The Biosciences  BIOINFORMATICS
, vol. 23, no. 2, pp. 512, 2007
Sort by:
Citations
(1)
On Approximate Jumbled Pattern Matching in Strings
Péter Burcsi
,
Ferdinando Cicalese
,
Gabriele Fici
,
Zsuzsanna Lipták
Journal:
Theory of Computing Systems / Mathematical Systems Theory  MST
, pp. 117