Palindromic Length in Linear Time
Palindromic Length in Linear Time
复制标题
线性时间的回文长度
DOI：
10.4230/lipics.cpm.2017.23
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Shur
中科院分区：
文献类型：
--
作者：
K. Borozdin;D. Kosolobov;Mikhail Rubinchik;A. Shur
一个字符串的回文长度是其串联等于这个字符串的回文的最小数目。求回文长度的问题引起了人们的关注，目前已有一些O（nlog n）时间的在线算法，本文给出了该问题的第一个线性时间在线算法。
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.