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.

string matching z algorithm

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.


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

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

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
      else            // if match not found loop out from inner for loop

      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

Related Contents to follow