Constructing LZ78 Tries and Position Heaps in Linear Time for Large Alphabets

Yuto Nakashima, Tomohiro I, Shunsuke Inenaga +2

We present the first worst-case linear-time algorithm to compute the Lempel-Ziv 78 factorization of a given string over an integer alphabet. Our algorithm is based on nearest marke…