Finding which strings in a set of strings have a certain prefix - can it be smaller than O(number of strings*length of prefix)
In the worst case, it has to be $n \cdot d$: You must check $d$ symbols of each of the $n$ strings to confirm they all start with the prefix, if you leave any out it might be different. This is essentially an adversarial argument.
You certainly can speed it up for non-matching strings, like comparing lengths, just check some positions to rule out prefixes. If the strings are random, checking just the first symbol will weed out all but a fraction of the strings (like the program you show does, bailing out early).
If you assume random strings over an alphabet of $m$ symbols, they will agree with the first $k$ symbols of your needle (which you are looking for in the haystack) $1/m^k$ of the times. The number of checks to do for each string will then be on average:
$\begin{align*}
   c
     &amp;= 1 + \sum_{2 \le k \le d} \frac{k}{m^k}
\end{align*}$
(you do $1$ check regardless, then $k$ more checks if $k$ symbols match).
To compute this sum, note that:
$\begin{align*}
  f(z)
    &amp;= \sum_{0 \le k \le d} \frac{z^k}{m^k} \\
    &amp;= \frac{1 - z^{k + 1} / m^{k + 1}}{1 - z / m} \\
    &amp;= \frac{m^{k + 1} - z^{k + 1}}{m^{k + 1} - z m^k}  \\
  f'(z)
    &amp;= \sum_{0 \le k \le d} \frac{k z^{k - 1}}{m^k} \\
  f'(1)
    &amp;= \sum_{0 \le k \le d} \frac{k}{m^k} \\
    &amp;= \frac{m^{d + 1} - (d + 1) m + d}{m^d (m - 1)^2} \\
  c
    &amp;= 1  + f'(1) \\
    &amp;= 1 + \frac{m^{d + 1} - (d + 1) m + d}{m^d (m - 1)^2}
\end{align*}$
Thus the number of symbol comparisons for one string is approximately $(m + 1) / m$, as you'd suspect.