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.

#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/



Related Contents to follow