Data Structures and Algorithms in C++, Second Edition

Chapter 12. Strings and Dynamic Programming

Contents

12.1 String Operations	554
12.1.1 The STL String Class	555
12.2 Dynamic Programming	557
12.2.1 Matrix Chain-Product	557
12.2.2 DNA and Text Sequence Alignment	560
12.3 Pattern Matching Algorithms	564
12.3.1 Brute Force	564
12.3.2 The Boyer-Moore Algorithm	566
12.3.3 The Knuth-Morris-Pratt Algorithm	570
12.4 Text Compression and the Greedy Method	575
12.4.1 The Huffman-Coding Algorithm	576
12.4.2 The Greedy Method	577
12.5 Tries	578
12.5.1 Standard Tries	578
12.5.2 Compressed Tries	582
12.5.3 Suffix Tries	584
12.5.4 Search Engines	586
12.6 Exercises	587

String Operations

Document processing is rapidly becoming one of the dominant functions of computers. Computers are used to edit documents, to search documents, to transport documents over the Internet, and to display documents on printers and computer screens. For example, the Internet document formats HTML and XML are primarily text formats, with added tags for multimedia content. Making sense of the many terabytes of information on the Internet requires a considerable amount of text processing.

In addition to having interesting applications, text processing algorithms also highlight some important algorithmic design patterns. In particular, the pattern matching problem gives rise to the brute-force method, which is often inefficient but has wide applicability. For text compression, we can apply the greedy method, which ...