The Number of Distinct Subpalindromes in Random Words

Mikhail Rubinchik, Arseny M. Shur

We prove that a random word of length $n$ over a $k$-ary fixed alphabet contains, on expectation, $\Theta (\sqrt{n})$ distinct palindromic factors. We study this number of factors, $E(n,…