Efficient algorithms for three variants of the LPF table

DOI10.1016/J.JDA.2011.02.002MaRDI QIDQ414447zbMATHOpenAlexFDO

Authors Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Wojciech Rytter, Tomasz Waleń

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

runspalindromesuffix arraylongest previous factorlongest previous non-overlapping factorlongest previous non-overlapping reverse factorlongest previous reverse factortext compression

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)

Recommendations

• Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays
• scientific article; zbMATH DE number 916038
• Faster algorithms for solving LPN
• Efficient algorithms for computing the $L_2$-discrepancy
• An efficient algorithm for 3NF determination
• An efficient algorithm for solving a special class of LP's
• An Improved LPN Algorithm
• Algorithm Theory - SWAT 2004
• Linear-space S-table algorithms for the longest common subsequence problem

Cites work

• scientific article; zbMATH DE number 3919857 (Why is no real title available?)
• scientific article; zbMATH DE number 2038766 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• scientific article; zbMATH DE number 2105038 (Why is no real title available?)
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• A universal algorithm for sequential data compression
• Algorithmic aspects of bioinformatics. Translated from the German original
• Algorithms on Strings
• Computing longest previous factor in linear time and applications
• Detecting leftmost maximal periodicities
• LPF computation revisited
• Lempel-Ziv factorization using less time \& space
• Linear Time Suffix Array Construction Using D-Critical Substrings
• Linear-time construction of suffix arrays (extended abstract)
• Searching for Gapped Palindromes
• Space efficient linear time construction of suffix arrays
• Succinct data structures for flexible text retrieval systems
• Suffix Arrays: A New Method for On-Line String Searches
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Transducers and repetitions

Cited in

(16)

• Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays
• Variations of the parameterized longest previous factor
• Reversing longest previous factor tables is hard
• Computing longest previous non-overlapping factors
• On parsing optimality for dictionary-based text compression -- the \texttt{Zip} case
• Computing longest previous factor in linear time and applications
• Parameterized longest previous factor
• A brief history of parameterized matching problems
• On the computation of longest previous non-overlapping factors
• Longest previous overlapping factor array
• Efficient approaches to compute longest previous non-overlapping factor array
• Longest previous non-overlapping factors table computation
• Parameterized longest previous factor
• A prefix array for parameterized strings
• Note on the greedy parsing optimality for dictionary-based text compression
• LPF computation revisited

This page was built for publication: Efficient algorithms for three variants of the LPF table

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414447)