 <p>A <a href="http://en.wikipedia.org/wiki/Trie" rel="nofollow noreferrer" title="Tries">trie (or prefix tree)</a> sounds right up your alley. It can do the search on a prefix string of length m in O(m) I believe.</p>