In software programming, it is very common to find a situation where we need to search for the occurrences of a specific pattern of characters in a bigger text. We are going to see some types of search algorithm that will help us with this task.
In order to explain them, first we are going to specify some assumptions:
The text is defined as an array
T[1..n], with length n, which contains chars.The pattern that we are searching for is defined as an array
P[1..m], with length m and m <= n.Where the pattern P exists in T, we call it shift s in T. In other words, the pattern P occurs in the s+1 position of the T array. So, this also implies that [1 < s < m-n] and also T[s+1 .. s+m] = P[1 .. m].
Look at the following figure to understand these concepts better:
Text, pattern, and shift example
The objective of every string matching algorithm is to find the different s positions in the text, T.