Pattern matching algorithms are very important in computer science. In this post we will discuss the simplest algorithm for pattern matching. Given some text and a pattern, we have to find where in the text, the pattern is found.

In this brute-force algorithm, we start matching the pattern from the beginning of the text. If a match is found we return the index. Otherwise we slide the matching window by one character and repeat the same process. For example if we are trying to find the pattern “ababb” in the text “abbabaababb“

The following depiction gives the steps involved in this algorithm

a b b a b a a b a b b

a b a

a

a

a b a b

a

a b

a b a b b — pattern found

The following is the C++ implementation of the above algorithm. Note that this algorithm finds only the first occurrence of the pattern. This can be modified to find all the occurrences also.

#include <iostream>

#include <cstring>

#define MAXLEN 100

using namespace std;

int findPattern(char *t, char *p)

{

int n = strlen(t); //length of the text

int m = strlen(p); //length of the pattern

int i,j; //loop counters

//outer loop tries to match the pattern from index 0 to (n-m)

for( i = 0 ; i <= n-m ; i++ )

{

//inner loop tries to match jth char in pattern

//with (i+j)th char in text

for( j = 0 ; j < m ; j++)

{

if( t[i+j] != p[j])

break;

}

//pattern found; return the index

if( j == m)

return i;

}

//pattern not found

return -1;

}

int main()

{

char text[MAXLEN];

char pattern[MAXLEN];

cin>>text;

cin>>pattern;

cout<<"pattern found at: "<<findPattern(text,pattern);

return 0;

}