TY - GEN
T1 - Computing left-right maximal generic words
AU - Nishimoto, Takaaki
AU - Nakashima, Yuto
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
AU - Takeda, Masayuki
N1 - Publisher Copyright:
© Czech Technical University in Prague, Czech Republic.
PY - 2015
Y1 - 2015
N2 - 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|, we want to compute all right-maximal extensions of P which occur in at least δ distinct documents. They proposed an O(n)-space data structure which can solve this problem in O(|P| + 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|, we want to compute all left-right-maximal extensions of P which occur in at least δ distinct documents. We propose an O(n log n)- space data structure which can solve this problem in O(|P| + occ log2 n + rocc log n) time where occ is the number of left-right-maximal extensions of P.
AB - 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|, we want to compute all right-maximal extensions of P which occur in at least δ distinct documents. They proposed an O(n)-space data structure which can solve this problem in O(|P| + 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|, we want to compute all left-right-maximal extensions of P which occur in at least δ distinct documents. We propose an O(n log n)- space data structure which can solve this problem in O(|P| + occ log2 n + rocc log n) time where occ is the number of left-right-maximal extensions of P.
UR - http://www.scopus.com/inward/record.url?scp=84978468616&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84978468616&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84978468616
T3 - Proceedings of the Prague Stringology Conference 2015, PSC 2015
SP - 5
EP - 16
BT - Proceedings of the Prague Stringology Conference 2015, PSC 2015
A2 - Zd'arek, Jan
A2 - Holub, Jan
PB - Prague Stringology Club
T2 - 19th Prague Stringology Conference, PSC 2015
Y2 - 24 August 2015 through 26 August 2015
ER -