TY - GEN

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

PY - 2013

Y1 - 2013

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 and height h that describes w, the first algorithm runs in O(nh(n + log N log n)) time and O(n2) space. Given the Lempel-Ziv 78 encoding of size s for w, the second algorithm runs in O(s log s) 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 and height h that describes w, the first algorithm runs in O(nh(n + log N log n)) time and O(n2) space. Given the Lempel-Ziv 78 encoding of size s for w, the second algorithm runs in O(s log s) time and space.

UR - http://www.scopus.com/inward/record.url?scp=84893901215&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893901215&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-02432-5_21

DO - 10.1007/978-3-319-02432-5_21

M3 - Conference contribution

AN - SCOPUS:84893901215

SN - 9783319024318

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 174

EP - 185

BT - String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings

PB - Springer Verlag

T2 - 20th International Symposium on String Processing and Information Retrieval, SPIRE 2013

Y2 - 7 October 2013 through 9 October 2013

ER -