Computation of String Repetition
Supaporn Chairungsee, Thana Charuphanthuset · 2016
We study the computation of the Longest Previous Factor (LPF) table which stores the maximal length of factors occuring at each position of a string. The Longest Previous Factor (LPF) table is useful for data compression and string algorithms. This table is related to a well-known technique for data compression, Ziv-Lempel factorization. We present an algorithm to compute the LPF table of a string from its augmented position heap. This algorithm can be applied for text compression and string algorithms. The algorithm is a linear time and a linear memory space.