TY - JOUR
T1 - Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
AU - I, Tomohiro
AU - Nakashima, Yuto
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
AU - Takeda, Masayuki
N1 - Publisher Copyright:
© 2016 Elsevier B.V.
PY - 2016/12/20
Y1 - 2016/12/20
N2 - We present two efficient algorithms which, given a compressed representation of a string w of length N, compute the Lyndon factorization of w. Given a straight line program (SLP) S of size n that describes w, the first algorithm runs in O(n2+P(n,N)+Q(n,N)nlogn) time and O(n2+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. Given the Lempel–Ziv 78 encoding of size s for w, the second algorithm runs in O(slogs) time and space.
AB - We present two efficient algorithms which, given a compressed representation of a string w of length N, compute the Lyndon factorization of w. Given a straight line program (SLP) S of size n that describes w, the first algorithm runs in O(n2+P(n,N)+Q(n,N)nlogn) time and O(n2+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. Given the Lempel–Ziv 78 encoding of size s for w, the second algorithm runs in O(slogs) time and space.
UR - http://www.scopus.com/inward/record.url?scp=84961175476&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84961175476&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2016.03.005
DO - 10.1016/j.tcs.2016.03.005
M3 - Article
AN - SCOPUS:84961175476
SN - 0304-3975
VL - 656
SP - 215
EP - 224
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -