TY - GEN
T1 - Lyndon factorization of grammar compressed texts revisited
AU - Furuya, Isamu
AU - Nakashima, Yuto
AU - I, Tomohiro
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
AU - Takeda, Masayuki
N1 - Funding Information:
Funding This work was supported by JSPS KAKENHI Grant Numbers JP17H06923 (YN), JP16K16009 (TI), JP17H01697 (SI), JP16H02783 (HB), and JP25240003 (MT).
Publisher Copyright:
© 2018 Yoshifumi Sakai; licensed under Creative Commons License CC-BY.
PY - 2018/5/1
Y1 - 2018/5/1
N2 - We revisit the problem of computing the Lyndon factorization of a string w of length N which is given as a straight line program (SLP) of size n. For this problem, we show a new algorithm which runs in O(P(n,N) + Q(n,N)n log logN) time and O(n logN + S(n,N)) space where P(n,N), S(n,N), Q(n,N) are respectively the pre-processing time, space, and query time of a data structure for longest common extensions (LCE) on SLPs. Our algorithm improves the algorithm proposed by I et al. (TCS '17), and can be more efficient than the O(N)-time solution by Duval (J. Algorithms '83) when w is highly compressible.
AB - We revisit the problem of computing the Lyndon factorization of a string w of length N which is given as a straight line program (SLP) of size n. For this problem, we show a new algorithm which runs in O(P(n,N) + Q(n,N)n log logN) time and O(n logN + S(n,N)) space where P(n,N), S(n,N), Q(n,N) are respectively the pre-processing time, space, and query time of a data structure for longest common extensions (LCE) on SLPs. Our algorithm improves the algorithm proposed by I et al. (TCS '17), and can be more efficient than the O(N)-time solution by Duval (J. Algorithms '83) when w is highly compressible.
UR - http://www.scopus.com/inward/record.url?scp=85048271134&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85048271134&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CPM.2018.24
DO - 10.4230/LIPIcs.CPM.2018.24
M3 - Conference contribution
AN - SCOPUS:85048271134
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 241
EP - 2410
BT - 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
A2 - Zhu, Binhai
A2 - Navarro, Gonzalo
A2 - Sankoff, David
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018
Y2 - 2 July 2018 through 4 July 2018
ER -