Computing longest previous non-overlapping factors

DOI10.1016/J.IPL.2010.12.005MaRDI QIDQ1944092zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Maxime Crochemore, German Tischler

Publication date 4 April 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.12.005

zbMATH Keywords

design of algorithmsdetection of repetitionslongest previous factorsuffix arraytext compressionZiv-Lempel factorisation

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 approaches to compute longest previous non-overlapping factor array
• Longest previous non-overlapping factors table computation
• Efficient algorithms for three variants of the LPF table
• Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays
• Computing longest previous factor in linear time and applications

Cites work

• A universal algorithm for sequential data compression
• Algorithms on Strings
• Computing longest previous factor in linear time and applications
• Crochemore Factorization of Sturmian and Other Infinite Words
• Detecting leftmost maximal periodicities
• Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays
• scientific article; zbMATH DE number 1786458 (Why is no real title available?)
• scientific article; zbMATH DE number 2105038 (Why is no real title available?)
• LPF computation revisited
• Permuted Longest-Common-Prefix Array
• Transducers and repetitions

Cited in

(17)

• Tighter bounds and optimal algorithms for all maximal -gapped repeats and palindromes. Finding all maximal -gapped repeats and palindromes in optimal worst case time on integer alphabets
• Longest previous non-overlapping factors table computation
• Computing the longest previous factor
• Variations of the parameterized longest previous factor
• Faster online computation of the succinct longest previous factor array
• A brief history of parameterized matching problems
• Longest previous overlapping factor array
• Longest -gapped repeat and palindrome
• An Online Algorithm for Finding the Longest Previous Factors
• LPF computation revisited
• Parameterized longest previous factor
• Efficient approaches to compute longest previous non-overlapping factor array
• A prefix array for parameterized strings
• Reversing longest previous factor tables is hard
• On the computation of longest previous non-overlapping factors
• Computing maximal-exponent factors in an overlap-free word
• Computing longest previous factor in linear time and applications

This page was built for publication: Computing longest previous non-overlapping factors

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