Computing longest previous non-overlapping factors

DOI10.1016/j.ipl.2010.12.005zbMath1260.68488OpenAlexW1968187010WikidataQ61677890 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 algorithmstext compressionsuffix arraylongest previous factordetection of repetitionsZiv-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)

Related Items

Longest previous overlapping factor array, Longest Gapped Repeats and Palindromes, Longest $$\alpha $$-Gapped Repeat and Palindrome, Variations of the parameterized longest previous factor, 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, Parameterized longest previous factor, 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
• 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