Name
Abstract | ||
|---|---|---|
The maximal generic words problem was proposed by Kucherov et al. (SPIRE 2012). Let D be a set of documents. In this problem, given a pattern P and a threshold d <= vertical bar D vertical bar, we want to compute all right-maximal extensions of P which occur in at least d distinct documents. They proposed an O(n)-space data structure which can solve this problem in O(vertical bar P vertical bar + rocc) time where n is the total length of documents in D and rocc is the number of right-maximal extensions of P. The data structure can be constructed in O(n) time. In this paper, we propose a more generalized problem. Given a pattern P and a threshold d <= vertical bar D vertical bar, we want to compute all left-right-maximal extensions of P which occur in at least d distinct documents. We propose an O(n log n)-space data structure which can solve this problem in O(vertical bar P vertical bar + occ log(2) n + rocc log n) time where occ is the number of left-right-maximal extensions of P. |
Year | Venue | Field |
|---|---|---|
2015 | PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2015 | Computer science,Theoretical computer science |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
3 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takaaki Nishimoto | 1 | 23 | 3.54 |
| Yuto Nakashima | 2 | 57 | 19.52 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |
| Hideo Bannai | 4 | 620 | 79.87 |
| Masayuki Takeda | 5 | 902 | 79.24 |