## string matching problem

Given a pattern P find all occurrence  of P in text T. For example if P = “aba ” and T = “bbabayababay’ ,then P occurs in T starting at positions 2, 6 and 8th index of  string T. look at the second occurrence at position 7 and third occurrence at position 9,This is called overlap of pattern P in text T.

## Naive Pattern Searching solution

Let us discus a naive solution of string pattern searching or matching.

From above figure we can say that string matching problem is a problem of finding all valid shifts of pattern p in given text T. The pattern P occurs in T starting at positions 3, 7 and 9.

```#include<stdio.h>
#include<string.h>

void search_pattern (char *p, char *t);

int
main ()
{
char *P = "aba";
char *T = "bbabayababay";
// do search
search_pattern (P, T);
return 0;
}

void
search_pattern (char *p, char *t)
{
int p_size = strlen (p);
int t_size = strlen (t);

int i = 0;
int j = 0;

// for each char in T

for (i = 0; i <= t_size; i++)
{
for (j = 0; j <= p_size; j++)
{
// compare ith char in T with jth char in P
if (*(t + i + j) == *(p + j))
{
// if match found continue for next possible match
// for compaison
continue;
}
else            // if match not found loop out from inner for loop
{
break;
}
}

if (j == p_size)        // if j is equal to pattern size
{
printf ("match found at %d \n", i);
}
}

}
```

## Now let discuss a very efficient string matching Z algorithm , follow this link

http://wikistack.com/cc-program-for-z-algorithm-string-matching/