Pattern Matching in Strings

A recurring problem in computing is determining whether a short string appears somewhere inside a longer one. This comes up in text editors searching for a word, antivirus software scanning for known signatures, DNA analysis looking for a genetic sequence, and search engines matching queries against documents. The short string being searched for is called the pattern, and the longer string being searched through is called the text.

Formally, the problem is: given a text of length n and a pattern of length m, find all positions in the text where the pattern occurs.

The naive approach

The most natural way to solve this problem requires no clever insight. The idea is to check every possible position in the text where the pattern could begin and, at each position, compare the pattern against the corresponding characters in the text one by one.

If all characters match, the pattern has been found at that position. If any character does not match, the attempt fails, and the search moves one position to the right.

This is called the naive algorithm, or the brute-force approach. It is the first solution most people think of, and understanding it well is the right starting point before moving to more sophisticated methods.

How it works

The algorithm follows a simple repeated process:

1. Let the text be the larger string and the pattern be the smaller string.

2. Consider each valid starting position in the text (starting from index ...