In

(Mathematical expressions are simplified in this html-dokument. They should be readable enough to get the flavour.)

We show that given a $k$-character query string and an array of $n$ strings arranged in alphabetical order, finding a matching string or report that no such string exists requires

O( k loglog n / loglog (4+k loglog n / log n)

+ k + log n)

character comparisons in the worst case, which is tight.