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

Get An Introduction to the Analysis of Algorithms, Second Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.