论文标题
纯线性时间中的alindromic k因子化
Palindromic k-Factorization in Pure Linear Time
论文作者
论文摘要
考虑到一般字母和整数$ k $的字符串$ s $的长度$ n $，问题是要确定$ s $是否是$ k $ nonepty palindromes的串联。该问题的两个先前已知的解决方案分别在$ o（kn）$和$ o（n \ log n）$中起作用。在这里，我们在Word-ram模型中解决了此问题的复杂性，并呈现了$ o（n）$ - 在线决定算法。该算法同时发现了弦分为非空心膜中的弦分中的最小奇数因子和最小因素数量。我们还演示了如何将$ s $的明确分解成$ k $ palindromes，并使用$ o（n）$ - 时间离线后处理。
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(n\log 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.
