Name
Abstract | ||
|---|---|---|
We present a compact semi-dynamic text index which allows us to find short patterns efficiently. For parameters (kle q le log _sigma n - log _sigma log _sigma n) and alphabet size (sigma = O(mathrm {polylog}(n))), all ( occ ) occurrences of a pattern of length at most (q-k+1) can be obtained in (O(k times occ + log _sigma n)) time, where (n) is the length of the text. Adding characters to the end of the text is supported in amortized constant time. Our index requires ((n/k) log (n/k) + n log sigma + o(n)) bits of space, which is compact (i.e., (O(n log sigma ))) when (k = varTheta (log _{sigma } n)). As a byproduct, we present a succinct van Emde Boas tree which supports insertion, deletion, predecessor, and successor on a dynamic set of integers over the universe ([0, m-1]) in (O(log log m)) time and requires only (m + o(m)) bits of space. |
Year | Venue | Field |
|---|---|---|
2015 | CPM | Integer,Discrete mathematics,Combinatorics,Computer science,Amortized analysis,Van Emde Boas tree,Suffix array,Sigma,Suffix tree,Alphabet |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
4 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yoshiaki Matsuoka | 1 | 0 | 0.68 |
| Tomohiro I | 2 | 148 | 22.06 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |
| Hideo Bannai | 4 | 620 | 79.87 |
| Masayuki Takeda | 5 | 902 | 79.24 |