Regarding the 3rd question, I will show this:

**Theorem.** For a random binary word of length $n$, the expected number of $h$th powers is
$$
\sim \frac{n}{2^{h-1}-1}.
$$
**Proof.** A basic event about occurrences of powers of a word in a binary word is
$$
S_{i,j,h} = \{w\in \{0,1\}^n \mid \text{$w$ has an $h$th power of length $h\cdot i$ ending in position $j$}\}
$$
$$
= \{w \mid w = av^hb, |av^h|=j, |v|=i\}
$$
We let $p$ denote the probability of 1 as opposed to 0; namely $p=1/2$. We may assume $w$ has odd length $n = 2k-1$.
Then $\mathbb P(S_{i,j,h}) = p^{(h-1)i}$, and the ranges for the variables are
$$
h\cdot i\le j\le 2k-1 = n
$$
Let $W_{n}$ be a uniformly distributed random word of length $n$, and let $s^{(c)}(w)$ be the number of $c$th powers in the word $w$.
So
$$
\mathbb E \sum_{j=hi}^{2k-1} \mathbf{1}_{S_{i,j,h}} = (2k-hi)p^{(h-1)i}
$$
is the expected number of $h$th powers of length $i$, for $hi\le 2k-1$.
Then
$$
\mathbb E s^{(h)}(W_{2k-1}) = \sum_{i=1}^{\lfloor(2k-1)/h\rfloor}(2k-hi)p^{(h-1)i}
$$
is the expected number of $h$th powers in a word of length $n=2k-1$.
Let us take $n\rightarrow\infty$ and divide by $n$; we get
$$ \sum_{i=1}^\infty p^{(h-1)i} = \frac{p^{h-1}}{1-p^{h-1}} = \frac1{2^{h-1}-1}
$$

**Corollary.** The expected number of squares, cubes, and 4th powers is $\sim n$, $n/3$, $n/7$, respectively.

The total number of nontrivial powers (squares and higher) overall will be something like
$$
n\cdot \sum_{h=2}^\infty \frac1{2^{h-1}-1}
$$
which is a Lambert series with value $\approx 1.606695n$.

every string. 2. Can do it through a linear scan, so $O(N)$. $\endgroup$4more comments