A subquadratic algorithm for minimum palindromic factorization

DOI10.1016/j.jda.2014.08.001zbMath1305.68382arXiv1403.2431OpenAlexW2022640981MaRDI QIDQ405573

Gabriele Fici, Juha Kärkkäinen, Travis Gagie, Dominik Kempa

Publication date: 5 September 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.2431

zbMATH Keywords

factorizationstring algorithmspalindromes

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (20)

Prefix palindromic length of the Thue-Morse word ⋮ Factorizing strings into repetitions ⋮ Diverse Palindromic Factorization Is NP-complete ⋮ Palindromic decompositions with gaps and errors ⋮ Palindromic length and reduction of powers ⋮ EERTREE: an efficient data structure for processing palindromes in strings ⋮ An efficient algorithm for the longest common palindromic subsequence problem ⋮ Palindromic length of words and morphisms in class \(\mathcal{P}\) ⋮ Maximal degenerate palindromes with gaps and mismatches ⋮ Algorithms and combinatorial properties on shortest unique palindromic substrings ⋮ Dynamic and internal longest common substring ⋮ Palindromic Decompositions with Gaps and Errors ⋮ Palindromic trees for a sliding window and its applications ⋮ Counting Palindromes in Substrings ⋮ Diverse Palindromic Factorization is NP-Complete ⋮ Greedy Palindromic Lengths ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the size of overlapping Lempel-Ziv and Lyndon factorizations ⋮ Comparing Degenerate Strings

Cites Work

• Unnamed Item
• On the least number of palindromes contained in an infinite word
• On palindromic factorization of words
• Parallel detection of all palindromes in a string
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• The derivation of on-line algorithms, with an application to finding palindromes
• Palindrome complexity.
• The Number of 1’s in Binary Integers: Bounds and Extremal Properties
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Algorithms on Strings, Trees and Sequences
• Computing Palindromic Factorizations and Palindromic Covers On-line
• Finding Palindromes: Variants and Algorithms

This page was built for publication: A subquadratic algorithm for minimum palindromic factorization