Palindromic k-Factorization in Pure Linear Time

Mikhail Rubinchik, Arseny M. Shur

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 kno…