String Indexing for Patterns with Wildcards

Details String Indexing for Patterns with Wildcards String Indexing for Patterns with Wildcards

2011-10-24

arxiv.org/abs/1110.5236v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the problem of indexing a string $t$ of length $n$ to report the occurrences of a query pattern $p$ containing $m$ characters and $j$ wildcards. Let $occ$ be the number of occurrences of $p$ in $t$, and $\sigma$ the size of the alphabet. We obtain the following results. - A linear space index with query time $O(m+\sigma^j \log \log n + occ)$. This significantly improves the previously best known linear space index by Lam et al. [ISAAC 2007], which requires query time $\Theta(jn)$ in the worst case. - An index with optimal query time $O(m+j+occ)$ using space $O(\sigma^{k^2} n \log^k \log n)$, where $k$ is the maximum number of wildcards allowed in the pattern. This is the first non-trivial bound with this query time. - A time-space trade-off, generalizing the index described by Cole et al. [STOC 2004]. Our results are obtained using a novel combination of well-known and new techniques, which could be of independent interest.

Affiliated with

Also associated with

No associations

Rating

String Indexing for Patterns with Wildcards does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with String Indexing for Patterns with Wildcards, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and String Indexing for Patterns with Wildcards will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-520691