Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(5)
Algorithm Design
Linear Time
Linear Time Algorithm
Suffix Array
lempel ziv
Related Publications
(5)
A Simple Algorithm for Computing the Lempel Ziv Factorization
Replacing suffix trees with enhanced suffix arrays
On Maximal Repetitions in Words
Fast and Practical Algorithms for Computing All the Runs in a String
Computing Quasi Suffix Arrays
Subscribe
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
Edit
Computing Longest Previous Factor in linear time and applications
(
Citations: 15
)
BibTex

RIS

RefWorks
Download
Maxime Crochemore
,
Lucian Ilie
We give two optimal lineartime 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 LempelZiv 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. 7580, 2008
DOI:
10.1016/j.ipl.2007.10.006
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.
(
www.sciencedirect.com
)
(
www.csd.uwo.ca
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(6)
...Reverse engineering for the Longest Previous Factor table, which is an important component of ZivLempel text compression method (see [
7
, 8]), is an open question...
Julien Clément
,
et 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. Smyth
,
et al.
Computing regularities in strings
...All runs in a string are computed using the lineartime algorithm of Kolpakov and Kucherov [7], where the Lempel–Ziv factorization is computed by the recent algorithm of Crochemore and Ilie [
3
]...
Maxime Crochemore
,
et 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 lineartime algorithms independently of the alphabet size (see [
5
])...
...algorithms have been proposed [1,
5
, 2] that use suffix arrays,a more spaceefficient 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 Crochemore
,
et 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 LZfactorization 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 LCParray...
...All LZfactorization 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 LCParray...
Enno Ohlebusch
,
et al.
LempelZiv Factorization Revisited
References
(16)
Replacing suffix trees with enhanced suffix arrays
(
Citations: 172
)
Mohamed Ibrahim Abouelhoda
,
Stefan Kurtz
,
Enno Ohlebusch
Journal:
Journal of Discrete Algorithms  JDA
, vol. 2, no. 1, pp. 5386, 2004
Fast and Practical Algorithms for Computing All the Runs in a String
(
Citations: 8
)
Gang Chen
,
Simon J. Puglisi
,
William F. Smyth
Conference:
Combinatorial Pattern Matching  CPM
, pp. 307315, 2007
Transducers and Repetitions
(
Citations: 146
)
Maxime Crochemore
Journal:
Theoretical Computer Science  TCS
, vol. 45, no. 1, pp. 6386, 1986
Lineartime computation of local periods
(
Citations: 7
)
Jeanpierre Duval
,
Roman Kolpakov
,
Gregory Kucherov
,
Thierry Lecroq
,
Arnaud Lefebvre
Journal:
Theoretical Computer Science  TCS
, vol. 326, no. 13, pp. 229240, 2004
Optimal Suffix Tree Construction with Large Alphabets
(
Citations: 167
)
Martin Farach
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 137143, 1997
Sort by:
Citations
(15)
The "runs" conjecture
(
Citations: 2
)
Maxime Crochemore
,
Lucian Ilie
,
Liviu Tinta
Journal:
Theoretical Computer Science  TCS
, vol. 412, no. 27, pp. 29312941, 2011
Removal of elemental mercury by bamboo charcoal impregnated with H 2O 2
Zengqiang Tan
,
Jianrong Qiu
,
Hancai Zeng
,
Hao Liu
,
Jun Xiang
Journal:
Fuel
, vol. 90, no. 4, pp. 14711475, 2011
Computing Longest Previous nonoverlapping Factors
Maxime Crochemore
,
German Tischler
Journal:
Information Processing Letters  IPL
, vol. 111, no. 6, pp. 291295, 2011
Counting distinct palindromes in a word in linear time
(
Citations: 1
)
Richard Groult
,
Élise Prieur
,
Gwénaël Richomme
Journal:
Information Processing Letters  IPL
, vol. 110, no. 20, pp. 908912, 2010
Repetitions in strings: Algorithms and combinatorics
(
Citations: 9
)
Maxime Crochemore
,
Lucian Ilie
,
Wojciech Rytter
Journal:
Theoretical Computer Science  TCS
, vol. 410, no. 50, pp. 52275235, 2009