O'Reilly logo

An Introduction to the Analysis of Algorithms, Second Edition by Philippe Flajolet, Robert Sedgewick

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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- ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required