Pattern matching

Pattern matching refers to the algorithmic problem of searching a (long) string, called a text, for substring matches of a collection of smaller strings, called patterns. In the case that there is only one pattern, pattern matching is known as motif searching.

We may search for exact pattern matches or allow for the case that patterns appear in the text with slight variations. The latter variant is particularly useful in biological applications (e.g., where the text is a genome and the patterns are known genes), which accounts for mutations that could have arisen on the genome.