13 citations · 37 across the 16 of their papers we have counts for
3 papers · 1 filter
Weighted ancestors in suffix trees
Pawel Gawrychowski, Moshe Lewenstein, Patrick K. Nicholson
The classical, ubiquitous, predecessor problem is to construct a data structure for a set of integers that supports fast predecessor queries. Its generalization to weighted trees,…
On Hardness of Jumbled Indexing
Amihood Amir, Timothy Chan, Moshe Lewenstein +1
Jumbled indexing is the problem of indexing a text for queries that ask whether there is a substring of matching a pattern represented as a Parikh vector, i.e., the vector…
Space-Efficient String Indexing for Wildcard Pattern Matching
Moshe Lewenstein, Yakov Nekrich, Jeffrey Scott Vitter
In this paper we describe compressed indexes that support pattern matching queries for strings with wildcards. For a constant size alphabet our data structure uses $O(n\log^{\varep…