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...