Chapter 15

Pattern Matching and Tries

Pattern matching and Tries are introduced along with terminology. The chapter discusses about Brute Force Algorithm, Boyer-Moore Algorithm and Knuth-Morris-Pratt Algorithm in detail along with examples and their applications. Categories of Tries namely standard tries, compressed tries and suffix tries and operations on them are explained clearly with applications.


In the day-to-day life of a computer user string matching has greater importance. During text editing, the user processes the text, organizes the text into sections and paragraphs and reorganizes the text very frequently. The text is searched to find a subtext or pattern and replace it with some other text. Efficiency of the ...

Get Data Structures and Algorithms Using C++ now with O’Reilly online learning.

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