O'Reilly logo

Data Structures and Algorithms in C++, Second Edition by David M. Mount, Roberto Tamassia, Michael T. Goodrich

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 12. Strings and Dynamic Programming

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

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