Pattern matching in strings

Abstract

The present chapter describes a few standard algorithms used for processing texts. They apply, for example, to the manipulation of texts (text editors), to the storage of textual data (text compression), and to data retrieval systems. The algorithms of the chapter are interesting in different respects. First, they are basic components used in the implementations of practical software. Second, they introduce programming methods that serve as paradigms in other fields of computer science (system or software design). Third, they play an important role in theoretical computer science by providing challenging problems.

Contents

• Matching fixed patterns
  (Brute force, Karp-Rabin, Knuth-Morris-Pratt,
  Boyer-Moore, Practical string matching, Aho-Corasick)
• Indexing texts (Suffix trees, Suffix automata)
• Research issues and summary

Note

This is Chapter 11 of the Algorithms and Theory of Computation Handbook edited by M. Atallah and published by CRC Press, Boca Raton (1998). The entire Handbook is roughly 1000 typeset pages, and is organized around the major subject areas of the discipline.