Consider random string of length $n$ over alphabet of size $|\mathcal{A}|=a$ ($a^n$ strings in total). What's expected number of distinct substrings of this string? What's expected number of distinct substrings of length $k$?

In other words, find size of the set $$\left\{(s, t)| s \in \mathcal{A}^n, t \in \mathcal{A} ^ k, t\ \text{is substring of}\ s \right\}.$$
Does it possible to calculate this number in polynomial time (i.e. $poly(n,k,a)$)?

I am looking for exact formula or alogirthm to calculate this number, but asymptotics results are also welcome.

The authors of this paper exactly answer that question (in corollary 2.2 of that paper).

It seems like if $\tau$ is a uniformly random word in $\mathcal{A}^n$, then $\tau$ has roughly as many distinct length $k$ substrings as possible (in expectation). That is, this number is within a constant factor of the upper bound $\min(a^k, n-k+1)$.

**Case 1 ($k$ is big):** As noted in the comments, if $k \geq (1+ \varepsilon) \log(n)/\log(a)$ , then with high probability no substring of length $k$ appears more than once. So in fact, when $k$ is this large, it is very likely that $\tau$ has exactly $n-k+1$ distinct substrings (no expectation needed).

**Case 2 ($k$ is small):** Suppose that $k < (1 + \varepsilon) \log(n)/\log(a)$. Then split the length $n$ word into $n/k$ disjoint blocks of length $k$. Let $B_1, B_2, \ldots , B_{n/k}$ denote the substrings of $\tau$ corresponding to these blocks. Then these $B_i$ are i.i.d. and each is uniformly drawn from $\mathcal{A}^k$. Thus, the expected number of distinct values for the $B_i$ is $a^k \left[ 1 - (1-a^{-k})^{n/k} \right] \geq a^k (1 - \exp[-\frac{n}{ka^k}])$, which is at least $a^k \delta$ for some fixed $\delta >0$ depending only on $\varepsilon$.

Does this answer the question to your satisfaction?

1more comment