String Matching Algorithm

String matching algorithm is a technique of matching some pattern from given text. A given string of n characters is called the text and a string of m characters is called the pattern (m<=n). Let, text T is denoted by t0….t(n-1) and pattern P is denoted by p0…..p(m-1).

The Brute force pattern matching algorithm is a simple pattern matching algorithm. The Brute force algorithm performs a checking, at all positions in the text between 0 and n-m, whether an occurance of the pattern starts there or not. Then, after each attempt, it shifts the pattern by exactly one position to the right.

If the match is found then it returns otherwise the matching process is continued by shifting one character to the right. If there is no match at all in the text for the given pattern even then we have to do m comparisons.

Algorithm:

Brute_Force_pattern(T[0….n-1], P[0,….m-1])

//Problem Description: this algorithm is for string matching

//Input: the array text T and pattern P

//Output: On successful search, the first position of matched pattern in the text is returned and on unsuccessful search -1 is returned.

for i<-0 to n-m do

{

j<-0

while j<m and P[j]=T[i+j] do

    j<-j+1

if  j<m

    return i

}

return -1

Solution:

Thus the pattern gets matched. The pattern is found at index 17 in text array.