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 Nine. Words and Mappings

STRINGS of characters from a fixed alphabet, or words, are of interest in a broad variety of applications beyond the types of algorithms considered in the previous chapter. In this chapter, we consider the same family of combinatorial objects studied in Chapter 8 (where we called them “bytestrings”), but from a different point of view.

A word may be viewed as a function taking an integer i in the interval 1 to N (the character position) into another integer j in the interval 1 to M (the character value, from an M-character alphabet). In the previous chapter, we primarily considered “local” properties, involving relationships among values associated with successive indices (correlations and so forth); in this chapter, ...

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