String Problems. How does your compiler look up a variable name in its symbol table? How does your help system quickly search that whole CD-ROM as you type in each character of your query string? How does a web search engine look up a phrase? These real problems use some of the techniques that we've glimpsed in the toy problems of this column.
Data Structures for Strings. We've seen several of the most important data structures used for representing strings.
Libraries or Custom-Made Components? The sets, maps and strings of the C++ STL were very convenient to use, but their general and powerful interface meant that they were not as efficient as a special-purpose hash function. Other library components were very efficient: hashing used strcmp and suffix arrays used qsort. I peeked at the library implementations of bsearch and strcmp to build the binary search and the wordncmp functions in the Markov program.
Copyright © 1999 Lucent Technologies. All rights reserved. Wed 18 Oct 2000