A subquadratic algorithm for minimum palindromic factorization

DOI10.1016/J.JDA.2014.08.001MaRDI QIDQ405573zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

factorizationstring algorithmspalindromes

Mathematics Subject Classification ID

Algorithms on strings (68W32)

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.

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

Cites work

• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Algorithms on Strings, Trees and Sequences
• Combinatorial properties of \(f\)-palindromes in the Thue-Morse sequence
• Computing palindromic factorizations and palindromic covers on-line
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Finding palindromes: variants and algorithms
• On palindromic factorization of words
• On the least number of palindromes contained in an infinite word
• Palindrome complexity.
• Parallel detection of all palindromes in a string
• The Number of 1’s in Binary Integers: Bounds and Extremal Properties
• The derivation of on-line algorithms, with an application to finding palindromes

Cited in

(21)

• Counting palindromes in substrings
• On the size of overlapping Lempel-Ziv and Lyndon factorizations
• Palindromic decompositions with gaps and errors
• scientific article; zbMATH DE number 7559452 (Why is no real title available?)
• Palindromic decompositions with gaps and errors
• An efficient algorithm for the longest common palindromic subsequence problem
• Comparing Degenerate Strings
• Diverse Palindromic Factorization Is NP-complete
• Degenerate string comparison and applications
• Factorizing strings into repetitions
• Algorithms and combinatorial properties on shortest unique palindromic substrings
• Computing palindromic factorizations and palindromic covers on-line
• Dynamic and internal longest common substring
• Prefix palindromic length of the Thue-Morse word
• Palindromic length and reduction of powers
• Palindromic length in linear time
• Maximal degenerate palindromes with gaps and mismatches
• Palindromic length of words and morphisms in class \(\mathcal{P}\)
• Palindromic trees for a sliding window and its applications
• Greedy palindromic lengths
• Diverse Palindromic Factorization is NP-Complete

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)