License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.81
URN: urn:nbn:de:0030-drops-127508
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12750/
Go to the corresponding LIPIcs Volume Portal

Rubinchik, Mikhail ; Shur, Arseny M.

Palindromic k-Factorization in Pure Linear Time

pdf-format:
LIPIcs-MFCS-2020-81.pdf (0.6 MB)

Abstract

Given a string s of length n over a general alphabet and an integer k, the problem is to decide whether s is a concatenation of k nonempty palindromes. Two previously known solutions for this problem work in time O(kn) and O(nlog n) respectively. Here we settle the complexity of this problem in the word-RAM model, presenting an O(n)-time online deciding algorithm. The algorithm simultaneously finds the minimum odd number of factors and the minimum even number of factors in a factorization of a string into nonempty palindromes. We also demonstrate how to get an explicit factorization of s into k palindromes with an O(n)-time offline postprocessing.

BibTeX - Entry

@InProceedings{rubinchik_et_al:LIPIcs:2020:12750,
  author =	{Mikhail Rubinchik and Arseny M. Shur},
  title =	{{Palindromic k-Factorization in Pure Linear Time}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{81:1--81:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ΔΎ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12750},
  URN =		{urn:nbn:de:0030-drops-127508},
  doi =		{10.4230/LIPIcs.MFCS.2020.81},
  annote =	{Keywords: stringology, palindrome, palindromic factorization, online algorithm}
}

Keywords: stringology, palindrome, palindromic factorization, online algorithm
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI