An Introduction to the Analysis of Algorithms, Second Edition

Chapter Eight. Strings and Tries

Sequences of characters or letters drawn from a fixed alphabet are called strings. Algorithms that process strings range from fundamental methods at the heart of the theory of computation to practical text-processing methods with a host of important applications. In this chapter, we study basic combinatorial properties of strings, some fundamental algorithms for searching for patterns in strings, and related data structures.

We use the term bitstring to refer to strings comprised of just two characters; if the alphabet is of size M > 2, we refer to the strings as bytestrings, or words, or M-ary strings. In this chapter, we assume that M is a small fixed constant, a reasonable assumption given our interest in text- ...