Name
Abstract | ||
|---|---|---|
The Longest Previous Factor array gives, for each position i in a string y, the length of the longest factor (substring) of y that occurs both at i and to the left of i in y. The Longest Previous Factor array is central in many text compression techniques as well as in the most efficient algorithms for detecting motifs and repetitions occurring in a text. Computing the Longest Previous Factor array requires usually the Suffix Array and the Longest Common Prefix array. We give the first time-space optimal algorithm that computes the Longest Previous Factor array, given the Suffix Array and the Longest Common Prefix array. We also give the first linear-time algorithm that computes the permutation that applied to the Longest Common Prefix array produces the Longest Previous Factor array. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.ejc.2012.07.011 | Eur. J. Comb. |
Keywords | Field | DocType |
string y,longest previous factor array,text compression technique,longest common prefix array,position i,linear-time algorithm,suffix array,time-space optimal algorithm,longest factor,efficient algorithm | LCP array,Discrete mathematics,Substring,Combinatorics,Text compression,Permutation,Suffix array,Longest repeated substring problem,Mathematics,Longest common substring problem | Journal |
Volume | Issue | ISSN |
34 | 1 | 0195-6698 |
Citations | PageRank | References |
8 | 0.54 | 20 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| Lucian Ilie | 2 | 840 | 76.50 |
| Costas S. Iliopoulos | 3 | 1534 | 167.43 |
| Marcin Kubica | 4 | 629 | 29.26 |
| Wojciech Rytter | 5 | 2290 | 181.52 |
| Tomasz Waleń | 6 | 706 | 39.62 |