string_pattern_match.h

/**
   String Pattern Matching:
   1, Brute Force Matching
   2, Boyer Moore Matching
   3, KMP Matching
   * * * * * * * * * * * * * 
   T: string size n
   P: pattern size m
   * * * * * * * * * * * * *
 **/
#include<string.h>

/* Naive Algorithm */
int matchBruteForce(char *T, char *P)
{
	int n = strlen(T), m = strlen(P);
	int i, j;

	for (i = 0; i <= n - m; i ++)
	{
	    j = 0;
		while (j < m && T[i + j] == P[j])
		{
			j++;
		}

		if (j == m)
		{
			return i; // return index match
		}
	}

	return -1; // not match
}

/* Boyer Moore Algorithm */
#include<stdlib.h>
#define NO_OF_CHARS 256

// make shift table (bad match table)
int* shift_table(char *P)
{
	int m = strlen(P);
	int *table = (int*) malloc(NO_OF_CHARS * sizeof(int));
	
	int i, j;

	for (i = 0; i < NO_OF_CHARS; i++)
	{
		table[i] = m;
		// for others chars and last char of P
	}

	for (j = 0; j < m - 1; j++)
	{
		table[P[j]] = m - 1 - j;
		// for pattern's indoor chars
	}

	return table;
}

// main algorithm
int matchBoyerMoore(char *T, char *P)
{
  int n = strlen(T), m = strlen(P);
	
  int matchCount; // number of matched chars
  int idx;
  int *shift = shift_table(P);

  idx = m-1;
  while (idx <= n - 1)
    {
      matchCount = 0;
      while (matchCount <= m - 1 &&
	     P[m - 1 - matchCount] == T[idx - matchCount])
	{
	  matchCount++;
	}

      if (matchCount == m)
	{
	  free(shift);
	  return idx - m + 1; // matched!
	}
      else
	{
	  idx += shift[T[idx]]; // shifted
	}
    }

  free(shift);
  return -1;
}

/* KMP Algorithm */
#include<stdlib.h>

int* prefix_table(char *P)
{
  int m = strlen(P);
  
  // pointer to prefix table
  int *table = (int*) malloc(m * sizeof(int));
  // initilize tablle
  table[0] = 0;

  int i = 1;
  int j = 0; // length of previous longest prefix
  
  while (i < m)
    {
      if (P[i] == P[j])
	{
	  table[i] = j + 1;
	  i++; j++;
	}
      else // P[i] != P[j]
	{
	  if (j > 0)
	    {
	      j = table[j - 1];
	    }
	  else // j == 0
 	    {
	      table[i] = 0; // no match
	      i++;
	    }
	}
    }
  
  return table;
}

int matchKMP(char *T, char *P)
{
  int n = strlen(T), m = strlen(P);
  int *pt = prefix_table(P);
  
  int i = 0, j = 0;
  while (i < n)
    {
      if (T[i] == P[j])
	{
	  if (j == m - 1) // travelled all of P
	    {
	      free(pt);
	      return i - j; // matched!
	    }
	  else
	    {
	      i++; j++;
	    }
	}
      else // T[i] != P[j]
	{
	  if (j > 0)
	    {
	      j = pt[j - 1];
	    }
	  else // j == 0
	    {
	      i++;
	    }
	}
    }
  
  free(pt);
  return -1;
}