A subquadratic algorithm for minimum palindromic factorization

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

doi:10.1016/j.jda.2014.08.001

A subquadratic algorithm for minimum palindromic factorization

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

Computer Science

University of Palermo
University of Helsinki

Research output: Contribution to journal › Article › peer-review

42 Scopus citations

Abstract

We give an O(n logn)-time, O(n)-space algorithm for factoring a string into the minimum number of palindromic substrings. That is, given a string S[1.n], in O(n logn) time our algorithm returns the minimum number of palindromes S ₁,...,S_ℓ such that S=S₁⋯S _ℓ. We also show that the time complexity is O(n) on average and Ω(n logn) in the worst case. The last result is based on a characterization of the palindromic structure of Zimin words.

Original language	English
Pages (from-to)	41-48
Number of pages	8
Journal	Journal of Discrete Algorithms
Volume	28
DOIs	https://doi.org/10.1016/j.jda.2014.08.001
State	Published - Sep 2014

Keywords

Factorization
Palindromes
String algorithms

Access to Document

10.1016/j.jda.2014.08.001

Cite this

@article{0c0e50b6198e4fe09c94758504412e88,

title = "A subquadratic algorithm for minimum palindromic factorization",

abstract = "We give an O(n logn)-time, O(n)-space algorithm for factoring a string into the minimum number of palindromic substrings. That is, given a string S[1.n], in O(n logn) time our algorithm returns the minimum number of palindromes S 1,...,Sℓ such that S=S1⋯S ℓ. We also show that the time complexity is O(n) on average and Ω(n logn) in the worst case. The last result is based on a characterization of the palindromic structure of Zimin words.",

keywords = "Factorization, Palindromes, String algorithms",

author = "Gabriele Fici and Travis Gagie and Juha K{\"a}rkk{\"a}inen and Dominik Kempa",

year = "2014",

month = sep,

doi = "10.1016/j.jda.2014.08.001",

language = "English",

volume = "28",

pages = "41--48",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

}

TY - JOUR

T1 - A subquadratic algorithm for minimum palindromic factorization

AU - Fici, Gabriele

AU - Gagie, Travis

AU - Kärkkäinen, Juha

AU - Kempa, Dominik

PY - 2014/9

Y1 - 2014/9

N2 - We give an O(n logn)-time, O(n)-space algorithm for factoring a string into the minimum number of palindromic substrings. That is, given a string S[1.n], in O(n logn) time our algorithm returns the minimum number of palindromes S 1,...,Sℓ such that S=S1⋯S ℓ. We also show that the time complexity is O(n) on average and Ω(n logn) in the worst case. The last result is based on a characterization of the palindromic structure of Zimin words.

AB - We give an O(n logn)-time, O(n)-space algorithm for factoring a string into the minimum number of palindromic substrings. That is, given a string S[1.n], in O(n logn) time our algorithm returns the minimum number of palindromes S 1,...,Sℓ such that S=S1⋯S ℓ. We also show that the time complexity is O(n) on average and Ω(n logn) in the worst case. The last result is based on a characterization of the palindromic structure of Zimin words.

KW - Factorization

KW - Palindromes

KW - String algorithms

UR - https://www.scopus.com/pages/publications/84907600335

U2 - 10.1016/j.jda.2014.08.001

DO - 10.1016/j.jda.2014.08.001

M3 - Article

AN - SCOPUS:84907600335

SN - 1570-8667

VL - 28

SP - 41

EP - 48

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

ER -

A subquadratic algorithm for minimum palindromic factorization

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this