display | more...

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.

Log in or register to write something here or to contact authors.