文章基本信息

标题：Palindromic k-Factorization in Pure Linear Time
本地全文：下载
作者：Mikhail Rubinchik ; Arseny M. Shur
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：170
页码：81:1-81:14
DOI：10.4230/LIPIcs.MFCS.2020.81
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：stringology; palindrome; palindromic factorization; online algorithm