Paper Info
Title
Efficient Lyndon Factorization Of Grammar Compressed Text
Abstract
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(n(4) + mn(3)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.
Year
DOI
Venue
2013
10.1007/978-3-642-38905-4_16
COMBINATORIAL PATTERN MATCHING
DocType
Volume
ISSN
Journal
7922
0302-9743
Citations 
PageRank 
References 
10
0.53
22
Authors
5
Name
Order
Citations
PageRank
Tomohiro I114822.06
Yuto Nakashima25719.52
Shunsuke Inenaga359579.02
Hideo Bannai462079.87
Masayuki Takeda590279.24