Name
Abstract | ||
|---|---|---|
The concept of a longest previous factor (LPF) is inherent to Ziv-Lempel factorization of strings in text compression, as well as in statistics of repetitions and symmetries. It is expressed in the form of a table - LPF[i] is the maximum length of a factor starting at position i, that also appears earlier in the given text. We show how to compute efficiently three new tables storing different variants of previous factors (past segments) of a string. The longest previous non-overlapping factor, for a given position i, is the longest factor starting at i which has an exact copy occurring entirely before, while the longest previous non-overlapping reverse factor for a given position i is the longest factor starting at i, such that its reverse copy occurs entirely before. In both problems the previous copies of the factors are required to occur within the prefix ending at position i-1. The longest previous (possibly overlapping) reverse factor is the longest factor starting at i, such that its reverse copy starts before i. These problems have not been explicitly considered before, but they have several applications and they are natural extensions of the longest previous factor problem, which has been extensively studied. Moreover, the newly introduced tables store additional information on the structure of the string, helpful to improve, for example, gapped palindrome detection and text compression using reverse factors. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.jda.2011.02.002 | J. Discrete Algorithms |
Keywords | Field | DocType |
suffix array,longest previous factor,position i,palindrome,longest previous non-overlapping reverse factor,lpf table,longest previous factor problem,efficient algorithm,reverse copy,previous factor,longest previous non-overlapping factor,longest previous reverse factor,runs,reverse factor,text compression,longest factor,longest previous non-overlapping reverse | Discrete mathematics,Combinatorics,Text compression,Palindrome,Algorithm,Suffix array,Prefix,Factorization,Longest repeated substring problem,Mathematics,Homogeneous space | Journal |
Volume | ISSN | Citations |
11, | Journal of Discrete Algorithms | 10 |
PageRank | References | Authors |
0.49 | 22 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| Costas S. Iliopoulos | 2 | 1534 | 167.43 |
| Marcin Kubica | 3 | 629 | 29.26 |
| Wojciech Rytter | 4 | 2290 | 181.52 |
| Tomasz Waleń | 5 | 706 | 39.62 |