Efficient algorithms for three variants of the LPF table
From MaRDI portal
Publication:414447
DOI10.1016/j.jda.2011.02.002zbMath1252.68358OpenAlexW2062386565MaRDI QIDQ414447
Costas S. Iliopoulos, Wojciech Rytter, Marcin Kubica, Maxime Crochemore, Tomasz Walen
Publication date: 11 May 2012
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2011.02.002
palindrometext compressionsuffix arrayrunslongest previous factorlongest previous non-overlapping factorlongest previous non-overlapping reverse factorlongest previous reverse factor
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)
Related Items
Longest previous overlapping factor array, On parsing optimality for dictionary-based text compression -- the \texttt{Zip} case, Variations of the parameterized longest previous factor, Note on the greedy parsing optimality for dictionary-based text compression, A prefix array for parameterized strings, A brief history of parameterized matching problems, A Linear-Time Algorithm for Seeds Computation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithmic aspects of bioinformatics. Translated from the German original
- Succinct data structures for flexible text retrieval systems
- Lempel-Ziv factorization using less time \& space
- Computing longest previous factor in linear time and applications
- Transducers and repetitions
- Detecting leftmost maximal periodicities
- Suffix Arrays: A New Method for On-Line String Searches
- Searching for Gapped Palindromes
- Linear-Time Construction of Suffix Arrays
- Space Efficient Linear Time Construction of Suffix Arrays
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- Linear Time Suffix Array Construction Using D-Critical Substrings
- LPF Computation Revisited
- A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
- A universal algorithm for sequential data compression
- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
- Algorithms on Strings
