powers in strings I have a feeling that the following question might have been studied: Suppose I have a finite alphabet $A,$ with $|A| = n,$ and a string $S$ of length $N.$ A string can be said to contain a $k$-th power, if 
$$S = S_1 S_2^k S_3,$$ where exponentiation means that $S_2$ is repeated $k$ times, and $S_1$ and $S_3$ might be empty. Let $P(n, N)$ be the function defined by: every string of length $N$ over an alphabet of length $n$ contains a $P(n, N)$-th power.
Now, the question(s):


*

*What is the (asymptotic) behavior of $P(n, N)?$

*Given a string $S$ as above, how hard is it to compute whether $S$ contains a $k$-th power?

*What can one say about random strings?

 A: regarding Question 2:
By Theorem 8.4.3 in M. Lothaire, Applied Combinatorics on Words and subsequent discussion, the number of $k$th powers in $S$ can be determined in time $O(N)$.
An algorithm for finding squares in DNA sequences has been implemented: http://bioinfo.lifl.fr/mreps//
A: 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$.
A: The comments have covered the bulk of the behaviour of P(n,N) for nontrivial values of n, showing that only when n=1 should P have values exceeding 2 (or n at most 2 to get a value more than 1).  A sorted suffix tree might help in improving the time bound suggested for searching for k powers, but the problem is clearly solvable in low degree polynomial time.
Regarding random strings, it is easiest to analyze powers of single letters as words of length L can
be considered as letters in an alphabet of size n^L.  The proportion of words of length N having a kth power in the first k letters is seen to be n^{1-k}, and although the probabilities of having a kth power of length k
starting at the cth character of a string of length N are not independent, the actual probability of having
a kth power in a string of length N greater than k is close to (N +1-k)n^{1-k} for small values of N, say N at most n^{k/2}.
