Computing longest previous non-overlapping factors

DOI10.1016/j.ipl.2010.12.005zbMath1260.68488WikidataQ61677890 ScholiaQ61677890MaRDI QIDQ1944092

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 algorithms; text compression; suffix array; longest previous factor; detection of repetitions; Ziv-Lempel factorisation

Mathematics Subject Classification ID

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

68W32: Algorithms on strings

Related Items

A Linear-Time Algorithm for Seeds Computation, Parameterized longest previous factor, A prefix array for parameterized strings, Computing maximal-exponent factors in an overlap-free word, Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets, Variations of the parameterized longest previous factor, A brief history of parameterized matching problems, Longest previous overlapping factor array, Longest Gapped Repeats and Palindromes, Longest $$\alpha $$-Gapped Repeat and Palindrome

Cites Work

• Unnamed Item
• Unnamed Item
• Computing longest previous factor in linear time and applications
• Transducers and repetitions
• Detecting leftmost maximal periodicities
• Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays
• Permuted Longest-Common-Prefix Array
• LPF Computation Revisited
• A universal algorithm for sequential data compression
• Algorithms on Strings
• Crochemore Factorization of Sturmian and Other Infinite Words