Computing longest previous factor in linear time and applications
From MaRDI portal
Publication:963336
DOI10.1016/j.ipl.2007.10.006zbMath1186.68591OpenAlexW1965743524WikidataQ56767309 ScholiaQ56767309MaRDI QIDQ963336
Maxime Crochemore, Lucian Ilie
Publication date: 19 April 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2007.10.006
analysis of algorithmsdesign of algorithmsstringssuffix arrayrepetitionslongest common prefixrunslongest previous factorLempel-Ziv factorization
Related Items
Factorizing strings into repetitions, Phenomenology of coupled nonlinear oscillators, Longest previous overlapping factor array, Locating maximal approximate runs in a string, LZRR: LZ77 parsing with right reference, On parsing optimality for dictionary-based text compression -- the \texttt{Zip} case, Variations of the parameterized longest previous factor, Counting distinct palindromes in a word in linear time, Towards a Solution to the “Runs” Conjecture, The three squares lemma revisited, Efficient algorithms for three variants of the LPF table, The “Runs” Theorem, Computing longest previous non-overlapping factors, Parameterized longest previous factor, Generalized substring compression, Note on the greedy parsing optimality for dictionary-based text compression, Speeding up the detection of tandem repeats over the edit distance, Algorithms and combinatorial properties on shortest unique palindromic substrings, Dictionary-symbolwise flexible parsing, Verifying and enumerating parameterized border arrays, An Online Algorithm for Finding the Longest Previous Factors, Using static suffix array in dynamic application: case of text compression by longest first substitution, Lempel-Ziv Factorization Revisited, A prefix array for parameterized strings, Efficient on-line repetition detection, Computing regularities in strings: a survey, Computing the longest previous factor, The ``runs conjecture, Unnamed Item, LZ77 computation based on the run-length encoded BWT, A brief history of parameterized matching problems, Repetitions in strings: algorithms and combinatorics, Faster online computation of the succinct longest previous factor array, Almost linear time computation of maximal repetitions in run length encoded strings, Lazy Lempel-Ziv Factorization Algorithms, String inference from longest-common-prefix array, Space-efficient representation of truncated suffix trees, with applications to Markov order estimation
Cites Work
- Unnamed Item
- Unnamed Item
- Linear-time computation of local periods
- Replacing suffix trees with enhanced suffix arrays
- Linear time algorithms for finding and representing all the tandem repeats in a string
- Transducers and repetitions
- Detecting leftmost maximal periodicities
- Constructing suffix arrays in linear time
- Space efficient linear time construction of suffix arrays
- Suffix Arrays: A New Method for On-Line String Searches
- Fast and Practical Algorithms for Computing All the Runs in a String
- On the Complexity of Finite Sequences
- A universal algorithm for sequential data compression
- Algorithms on Strings
