1 Search Results for "Borozdin, Kirill"

Document
DOI: 10.4230/LIPIcs.CPM.2017.23
Palindromic Length in Linear Time

Authors: Kirill Borozdin, Dmitry Kosolobov, Mikhail Rubinchik, and Arseny M. Shur

Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)

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.
Cite as

Kirill Borozdin, Dmitry Kosolobov, Mikhail Rubinchik, and Arseny M. Shur. Palindromic Length in Linear Time. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 23:1-23:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{borozdin_et_al:LIPIcs.CPM.2017.23,
  author =	{Borozdin, Kirill and Kosolobov, Dmitry and Rubinchik, Mikhail and Shur, Arseny M.},
  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 =	{K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.23},
  URN =		{urn:nbn:de:0030-drops-73389},
  doi =		{10.4230/LIPIcs.CPM.2017.23},
  annote =	{Keywords: palindrome, palindromic length, palindromic factorization, online}
}
  • Refine by Author
  • 1 Borozdin, Kirill
  • 1 Kosolobov, Dmitry
  • 1 Rubinchik, Mikhail
  • 1 Shur, Arseny M.

  • Refine by Classification

  • Refine by Keyword
  • 1 online
  • 1 palindrome
  • 1 palindromic factorization
  • 1 palindromic length

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact