 |
HAL UPEC - UPEM Portal |  |
 |
Conference papers
LPF computation revisited
Abstract : We present efficient algorithms for storing past segments of a text. They are computed using two previously computed read-only arrays (SUF and LCP) composing the Suffix Array of the text. They compute the maximal length of the previous factor (subword) occurring at each position of the text in a table called LPF. This notion is central both in many conservative text compression techniques and in the most efficient algorithms for detecting motifs and repetitions occurring in a text. The main results are: a linear-time algorithm that computes explicitly the permutation that transforms the LCP table into the LPF table; a time-space optimal computation of the LPF table; and an O(n log n) strong in-place computation of the LPF table.
Cited literature [21 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-00741881
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 11:38:47 AM
Last modification on : Tuesday, October 19, 2021 - 11:26:18 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:03 AM
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, February 13, 2013 - 11:38:47 AM
Last modification on : Tuesday, October 19, 2021 - 11:26:18 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 4:00:03 AM
File
LPF_computation_revisited.pdf
Files produced by the author(s)