Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
复制标题
DOI：
10.1016/j.tcs.2016.03.005
复制
发表时间：
2016-12
期刊：
影响因子：
--
通讯作者：
I. Tomohiro;Yuto Nakashima;Shunsuke Inenaga;H. Bannai;M. Takeda
中科院分区：
文献类型：
--
作者：
I. Tomohiro;Yuto Nakashima;Shunsuke Inenaga;H. Bannai;M. Takeda
我们提出了两种有效的算法，给定长度为 N 的字符串 w 的压缩表示，计算 w 的 Lyndon 分解。给定描述 w 的大小为 n 的直线程序 (SLP) S，第一个算法在 O (n 2+ P (n, N)+ Q (n, N) n log n) 时间和 O (n 2+ S (n, N)) 空间中运行，其中 P (n, N)、S (n, N)、Q (n, N) 分别是 SLP 上最长公共扩展 (LCE) 的数据结构的预处理时间、空间和查询时间。给定 w 的大小为 s 的 Lempel-Ziv 78 编码，第二个算法在 O (s log s) 时间和空间中运行。
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 (n 2+ P (n, N)+ Q (n, N) n log n) time and O (n 2+ 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 (s log s) time and space.