Academic
Publications
Computing Longest Previous Factor in linear time and applications

Computing Longest Previous Factor in linear time and applications,10.1016/j.ipl.2007.10.006,Information Processing Letters,Maxime Crochemore,Lucian Il

Computing Longest Previous Factor in linear time and applications   (Citations: 15)
BibTex | RIS | RefWorks Download
We give two optimal linear-time algorithms for computing the Longest Previous Factor (LPF) array corresponding to a string w. For any position i in w, LPF(i) gives the length of the longest factor of w starting at position i that occurs previously in w. Several properties and applications of LPF are investigated. They include computing the Lempel-Ziv factorization of a string and detecting all repetitions (runs) in a string in linear time independently of the integer alphabet size.
Journal: Information Processing Letters - IPL , vol. 106, no. 2, pp. 75-80, 2008
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Reverse engineering for the Longest Previous Factor table, which is an important component of Ziv-Lempel text compression method (see [7, 8]), is an open question...

    Julien Clémentet al. Reverse Engineering Prefix Tables

    • ...The Longest Previous Factor (LPF) array was introduced in [10], but also appears as the prefix array π in [15]...
    • ...For any position i in a string x, LPF[i] is defined to be the length of the longest factor of x starting at position i that occurs previously in x. Formally, [10] defines LPF[i] as follows:...
    • ...For an example of LPF, see column 5 of Figure 3. It is shown in [10] that LPF is a permutation of LCP...

    W. F. Smythet al. Computing regularities in strings

    • ...All runs in a string are computed using the linear-time algorithm of Kolpakov and Kucherov [7], where the Lempel–Ziv factorization is computed by the recent algorithm of Crochemore and Ilie [3]...

    Maxime Crochemoreet al. Towards a Solution to the "Runs" Conjecture

    • ...A typical application of this idea resides in algorithms to compute repetitions in strings, such as Kolpakov and Kucherov algorithm for reporting all maximal repetitions [15], and indeed it seems to be the only technique that leads to linear-time algorithms independently of the alphabet size (see [5])...
    • ...algorithms have been proposed [1, 5, 2] that use suffix arrays,a more space-efficient structure...
    • ...We improve here the simplest of those, that of [5], so that it uses o(n) additional space as opposed to O(n) of [5]...
    • ...We improve here the simplest of those, that of [5], so that it uses o(n) additional space as opposed to O(n) of [5]...
    • ...LPF[i] = max {ℓ | w[i..i + ℓ − 1] is a factor of w[0..i + ℓ − 2]} ∪ {0} � . LPF was introduced in [5], but appears also as the λ array in [8]...
    • ...The Lempel–Ziv factorization is then easily computed from LPF by the algorithm of Fig. 2, already proposed in [5]...
    • ...In order to explain the idea for the computation of LPF, it is helpful to arrange the SA and LCP arrays in a graph, as done in [5]...
    • ...The difference between this algorithm and the one of [5] starts with the fact that the latter uses only the case (i) above...
    • ...First, all features of the algorithm of [5] are preserved...
    • ...Another one, the algorithm of [5] computes also the PrevOcc array, which gives a previous position where a factor of length LPF[i] starts...

    Maxime Crochemoreet al. A Simple Algorithm for Computing the Lempel Ziv Factorization

    • ...Recently, several algorithms have been developed that use suffix arrays instead [1,4,5,7,6]...
    • ...We now recall the nice (conceptual) graph representation of SA and LCP introduced in [5]...
    • ...The algorithm of Crochemore and Ilie [5] scans the arrays SA and LCP from left to right...
    • ...All LZ-factorization algorithms in [1,4,5,7,6] except for the first one in [5] and the last two in [4] rely on the suffix array and the precomputed LCP-array...
    • ...All LZ-factorization algorithms in [1,4,5,7,6] except for the first one in [5] and the last two in [4] rely on the suffix array and the precomputed LCP-array...

    Enno Ohlebuschet al. Lempel-Ziv Factorization Revisited

Sort by: