Naive Search Algorithm

The string matching problem has two inputs, as follows:

• An arrayT[1, 2, ...n]of lengthn
• An arrayP[1, 2, ...m]of lengthm (<= n)

The elements of T and P are characters from the same finite alphabet (usually called ∑).

For instance, we may be searching in binary strings, in which case our alphabet is {0, 1}, or we may be searching in strings of lowercase letters, in which case our alphabet is {a, b… z}.

The following diagram represents this terminology:

Figure 5.1: Representation of text arrayT, pattern arrayP, and finite alphabet ∑

The character arrays P and T are usually called "strings of characters". We're interested in finding occurrences of pattern P in text T.

We say that pattern P occurs in text T if we can align the pattern P with text T so that all characters in P match the ones in T. When aligning, we need to shift pattern P zero or more times to the right.

Therefore, in the string matching problem, we're interested in valid shifts with which pattern P occurs in...