Efficient algorithms for three variants of the LPF table

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

zbMATH Keywords

palindrometext compressionsuffix arrayrunslongest previous factorlongest previous non-overlapping factorlongest previous non-overlapping reverse factorlongest previous reverse factor

Mathematics Subject Classification ID

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