Abstract.
Given a k-character query string and an array of n strings arranged in lexicographical order, computing the rank of the query string among the n strings or deciding whether it occurs in the array requires the inspection of
Key words. string searching, character comparisons, dictionaries, potential functions, lower bounds
AMS Subject Classifications. 68Q17, 68Q25, 68W05, 68W40
$$ \Theta\left( \frac {k\log {\log n}} {\log {\log {(4+\frac{k \log{\log n}}{\log n})}}}+k+\log n\right) $$
characters in the worst case.