Exact string matching is a classic computer science problem with a myriad of approaches for a quick solution.

#### The Problem

Given a string P called the *pattern* and a longer string T called the *text*, the exact string matching problem is to find all occurrences, if any, of pattern P in text T.

#### Importance of the Problem

The importance of the problem should be obvious to anyone using a computer. Ever searched a long text document to find a particular term? Ever used a world wide web search engine? Ever done any type of research involving any sort of online database? If so, you've used an implementation of the solution to this problem.

#### Solving the Problem

The obvious solution to the problem is the naive solution. Start by aligning the left end of pattern P with the left end of pattern T and compare characters until either two characters do not match or P is exhausted (i.e., a match is found). Then, shift P one character to the right in comparison with T and compare again. This solution is very slow, requiring on the order of P*P operations plus a significantly large constant.

A great deal of research has been done into exact string matching, and some excellent algorithms have been uncovered. Among these are Z, Boyer-Moore, KMP, real-time matching, Apostolico-Giancarlo, shift-and, suffix trees, suffix arrays, and several more. Each of these has its own body of research in and of itself.