moestr.cpp
//Searching String Using Boyer-Moore Algorithm

Searching String Using Boyer-Moore Algorithm
Searching String Using Boyer - Moore Algorithm
int Str_BM(char* str, char* sub)
{
	int c = Str_Len(sub);
	int i = 0, j = 0;
	int *m = (int*)malloc(256 * sizeof(int));
	int *n = (int*)malloc(c * sizeof(int));
	int *o = (int*)malloc(c * sizeof(int));
	if (!(m&&n))
	{
		if (m)free(m);
		if (n)free(n);
		return(-1);
	}
	for (; i < 256; m[i] = c, i++);
	j = c - 1;
	for (i = 0; i < c; i++)
	{
		if (m[sub[j - i]]>i)m[sub[j - i]] = i;
	}
	i = c - 1;
	j = c - 2;
	n[i] = 1;
	o[i] = 0;
	o[j] = 0;
	while (j > 0)
	{
		n[j] = c;
		if (sub[i] == sub[j])
		{
			i--;
			j--;
			o[j] = c - 1 - i;
			if (sub[i] != sub[j])
			{
				n[i] = i - j;
				i = c - 1 - o[i];
			}
		}
		else
		{
			i = c - 1;
			j--;
			o[j] = 0;
		}
	}
	if (i != c - 1)
	{
		j = i - j;
		while (i > 0)
		{
			i--;
			n[i] = j;
		}
	}
	else
	{
		n[j] = i;
	}
	free(o);
	i = 0;
	while (str[i] != '\0')
	{
		for (j = c - 1; str[i + j] == sub[j]; j--)
		{
			if (j == 0)
			{
				free(m);
				free(n);
				return(i);
			}
		}
		if (m[str[i + j]] > n[j + 1])
		{
			i += m[str[i + j]];
		}
		else
		{
			i += n[j];
		}
	}
	free(m);
	free(n);
	return(-1);
}
int Str_BM ( char * str , char * sub ) { int c = Str_Len ( sub ) ; int i = 0 , j = 0 ; int * m = ( int * ) malloc ( 256 * sizeof ( int ) ) ; int * n = ( int * ) malloc ( c * sizeof ( int ) ) ; int * o = ( int * ) malloc ( c * sizeof ( int ) ) ; if ( ! ( m && n ) ) { if ( m ) free ( m ) ; if ( n ) free ( n ) ; return ( -1 ) ; } for ( ; i < 256 ; m [ i ] = c , i ++ ) ; j = c - 1 ; for ( i = 0 ; i < c ; i ++ ) { if ( m [ sub [ j - i ] ] > i ) m [ sub [ j - i ] ] = i ; } i = c - 1 ; j = c - 2 ; n [ i ] = 1 ; o [ i ] = 0 ; o [ j ] = 0 ; while ( j > 0 ) { n [ j ] = c ; if ( sub [ i ] == sub [ j ] ) { i -- ; j -- ; o [ j ] = c - 1 - i ; if ( sub [ i ] != sub [ j ] ) { n [ i ] = i - j ; i = c - 1 - o [ i ] ; } } else { i = c - 1 ; j -- ; o [ j ] = 0 ; } } if ( i != c - 1 ) { j = i - j ; while ( i > 0 ) { i -- ; n [ i ] = j ; } } else { n [ j ] = i ; } free ( o ) ; i = 0 ; while ( str [ i ] != ' \0 ' ) { for ( j = c - 1 ; str [ i + j ] == sub [ j ] ; j -- ) { if ( j == 0 ) { free ( m ) ; free ( n ) ; return ( i ) ; } } if ( m [ str [ i + j ] ] > n [ j + 1 ] ) { i += m [ str [ i + j ] ] ; } else { i += n [ j ] ; } } free ( m ) ; free ( n ) ; return ( -1 ) ; }
Searching String Using Boyer-Moore Algorithm
Searching String Using Boyer - Moore Algorithm
//processing for the bc array
 //processing for the gs array
 //for case 1
 //for case 2
 //finding the string
