TY - GEN
T1 - Efficient Lyndon factorization of grammar compressed text
AU - I, Tomohiro
AU - Nakashima, Yuto
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
AU - Takeda, Masayuki
PY - 2013
Y1 - 2013
N2 - We present an algorithm for computing the Lyndon factorization of a string that is given in grammar compressed form, namely, a Straight Line Program (SLP). The algorithm runs in O(n4 + mn3 h) time and O(n 2) space, where m is the size of the Lyndon factorization, n is the size of the SLP, and h is the height of the derivation tree of the SLP. Since the length of the decompressed string can be exponentially large w.r.t. n, m and h, our result is the first polynomial time solution when the string is given as SLP.
AB - We present an algorithm for computing the Lyndon factorization of a string that is given in grammar compressed form, namely, a Straight Line Program (SLP). The algorithm runs in O(n4 + mn3 h) time and O(n 2) space, where m is the size of the Lyndon factorization, n is the size of the SLP, and h is the height of the derivation tree of the SLP. Since the length of the decompressed string can be exponentially large w.r.t. n, m and h, our result is the first polynomial time solution when the string is given as SLP.
UR - http://www.scopus.com/inward/record.url?scp=84884303289&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84884303289&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-38905-4_16
DO - 10.1007/978-3-642-38905-4_16
M3 - Conference contribution
AN - SCOPUS:84884303289
SN - 9783642389047
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 153
EP - 164
BT - Combinatorial Pattern Matching - 24th Annual Symposium, CPM 2013, Proceedings
PB - Springer Verlag
T2 - 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013
Y2 - 17 June 2013 through 19 June 2013
ER -