Computing longest previous factor in linear time and applications. (English) Zbl 1186.68591
Summary: 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.
MSC:
| 68W40 | Analysis of algorithms |
Keywords:
design of algorithms; analysis of algorithms; strings; suffix array; longest common prefix; longest previous factor; Lempel-Ziv factorization; repetitions; runsReferences:
| [1] | Abouelhoda, M. I.; Kurtz, S.; Ohlenbusch, E., Replacing suffix trees with enhanced suffix arrays, J. Discrete Algorithms, 2, 53-86 (2004) · Zbl 1115.92303 |
| [2] | Chen, G.; Puglisi, S. J.; Smyth, W. F., Fast and practical algorithms for computing all runs in a string, (Proc. of CPM’07. Proc. of CPM’07, Lecture Notes in Comput. Sci., vol. 4580 (July 2007), Springer: Springer Berlin), 307-315 · Zbl 1138.68658 |
| [3] | Crochemore, M., Transducers and repetitions, Theoret. Comput. Sci., 45, 1, 63-86 (1986) · Zbl 0615.68053 |
| [4] | Crochemore, M.; Hancart, C.; Lecroq, T., Algorithms on Strings (2007), Cambridge Univ. Press · Zbl 1137.68060 |
| [5] | M. Crochemore, L. Ilie, Computing local periodicities in strings, invited talk, in: AutoMathA’07, Palermo, Italy, June 2007; M. Crochemore, L. Ilie, Computing local periodicities in strings, invited talk, in: AutoMathA’07, Palermo, Italy, June 2007 |
| [6] | Duval, J.-P.; Kolpakov, R.; Kucherov, G.; Lecroq, T.; Lefebvre, A., Linear-time computation of local periods, Theoret. Comput. Sci., 326, 1-3, 229-240 (2004) · Zbl 1071.68087 |
| [7] | Farach, M., Optimal suffix tree construction with large alphabets, (Proc. of FOCS’97 (1997), IEEE Computer Society Press), 137-143 |
| [8] | Gusfield, D.; Stoye, J., Linear time algorithm for finding and representing all the tandem repeats in a string, J. Comput. System Sci., 69, 525-546 (2004) · Zbl 1076.68111 |
| [9] | Kärkkäinen, J.; Sanders, P., Simple linear work suffix array construction, (Proc. of ICALP’03. Proc. of ICALP’03, Lecture Notes in Comput. Sci., vol. 2719 (2003), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 943-955 · Zbl 1039.68042 |
| [10] | Kasai, T.; Lee, G.; Arimura, H.; Arikawa, S.; Park, K., Linear-time longest-common-prefix computation in suffix arrays and its applications, (Proc. of CPM’01. Proc. of CPM’01, Lecture Notes in Comput. Sci., vol. 2089 (2001), Springer-Verlag: Springer-Verlag Berlin), 181-192 · Zbl 0990.68639 |
| [11] | Kim, D. K.; Sim, J. S.; Park, H.; Park, K., Constructing suffix arrays in linear time, J. Discrete Algorithms, 3, 2-4, 126-142 (2005) · Zbl 1101.68505 |
| [12] | Ko, P.; Aluru, S., Space efficient linear time construction of suffix arrays, J. Discrete Algorithms, 3, 2-4, 143-156 (2005) · Zbl 1101.68506 |
| [13] | Kolpakov, R.; Kucherov, G., Finding maximal repetitions in a word in linear time, (Proc. of FOCS’99 (1999), IEEE Computer Society Press), 596-604 |
| [14] | Lempel, A.; Ziv, J., On the complexity of finite sequences, IEEE Trans. Inform. Theory, 92, 1, 75-81 (1976) · Zbl 0337.94013 |
| [15] | Main, M. G., Detecting leftmost maximal periodicities, Discrete Appl. Math., 25, 145-153 (1989) · Zbl 0683.68033 |
| [16] | Manber, U.; Myers, G., Suffix arrays: a new method for on-line search, SIAM J. Comput., 22, 5, 935-948 (1993) · Zbl 0784.68027 |
| [17] | Ziv, J.; Lempel, A., A universal algorithm for sequential data compression, IEEE Trans. Inform. Theory, 23, 3, 337-343 (1977) · Zbl 0379.94010 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
