The string matching problem has two inputs, as follows:

- An array
*T[1, 2, ...n]*of length*n* - An
*array**P[1, 2, ...m]*of length*m (<= 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...