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