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.CPM.2017.23
URN: urn:nbn:de:0030-drops-73389
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7338/
Go to the corresponding LIPIcs Volume Portal

Borozdin, Kirill ; Kosolobov, Dmitry ; Rubinchik, Mikhail ; Shur, Arseny M.

Palindromic Length in Linear Time

pdf-format:
LIPIcs-CPM-2017-23.pdf (0.5 MB)

Abstract

Palindromic length of a string is the minimum number of palindromes whose concatenation is equal to this string. The problem of finding the palindromic length drew some attention, and a few O(n log n) time online algorithms were recently designed for it. In this paper we present the first linear time online algorithm for this problem.

BibTeX - Entry

@InProceedings{borozdin_et_al:LIPIcs:2017:7338,
  author =	{Kirill Borozdin and Dmitry Kosolobov and Mikhail Rubinchik and Arseny M. Shur},
  title =	{{Palindromic Length in Linear Time}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{23:1--23:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{Juha K{\"a}rkk{\"a}inen and Jakub Radoszewski and Wojciech Rytter},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7338},
  URN =		{urn:nbn:de:0030-drops-73389},
  doi =		{10.4230/LIPIcs.CPM.2017.23},
  annote =	{Keywords: palindrome, palindromic length, palindromic factorization, online}
}

Keywords: palindrome, palindromic length, palindromic factorization, online
Collection: 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Issue Date: 2017
Date of publication: 30.06.2017

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