Abstract

We examine the computation of the Longest Previous non-overlapping Factor (LPnF) table. The LPnF table is the table that stores the maximal length of factors re-occurring at each position of a string without overlapping. The LPnF table is related to well-known techniques for data compression, such as Ziv-Lempel factorization. This table is useful both for string algorithms and for text compression. In this paper, we present two algorithms to compute the LPnF table of a string: one from its augmented position heap and the other from its suffix heap. The proposed algorithms run in linear time with linear memory space.