A subquadratic algorithm for minimum palindromic factorization

DOI10.1016/J.JDA.2014.08.001zbMATH Open1305.68382arXiv1403.2431OpenAlexW2022640981MaRDI QIDQ405573FDOQ405573

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

Publication date: 5 September 2014

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

Abstract: We give an $mathcalO(nlogn)$-time, $mathcalO(n)$-space algorithm for factoring a string into the minimum number of palindromic substrings. That is, given a string $S[\mathrm{1..}n]$, in $mathcalO(nlogn)$ time our algorithm returns the minimum number of palindromes $S_1,ldots,S_{e}ll$ such that $S=S_{1}cdots{S}_{e}ll$. We also show that the time complexity is $mathcalO(n)$ on average and $Omega(nlogn)$ in the worst case. The last result is based on a characterization of the palindromic structure of Zimin words.

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

Recommendations

• scientific article; zbMATH DE number 7559452
• Recent advances of palindromic factorization
• Subquadratic-time factoring of polynomials over finite fields
• scientific article; zbMATH DE number 1263216
• Algorithms and combinatorial properties on shortest unique palindromic substrings
• The palindromic cyclic reduction and related algorithms
• Computing palindromic factorizations and palindromic covers on-line
• A subquadratic algorithm for the simultaneous conjugacy problem
• Smallest and Largest Block Palindrome Factorizations
• Diverse Palindromic Factorization is NP-Complete

zbMATH Keywords

factorizationstring algorithmspalindromes

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

• Algorithms on Strings, Trees and Sequences
• Palindrome complexity.
• On the least number of palindromes contained in an infinite word
• Combinatorial properties of \(f\)-palindromes in the Thue-Morse sequence
• On palindromic factorization of words
• 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
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• The derivation of on-line algorithms, with an application to finding palindromes
• Computing Palindromic Factorizations and Palindromic Covers On-line
• Finding Palindromes: Variants and Algorithms
• Parallel detection of all palindromes in a string

Cited In (20)

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

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

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