Boyer-Moore Algorithm

boyermoorematch.c

int  boyermoorematch(char S[ ], char P[ ])‏
{
	int n, m, i, j, lastch;  n = strlen(S);  m = strlen(P);
	i = m – 1; j = m – 1;
	while  (i < n) 		//  not end of string S
		if  (P[j] == S[i])  
			if  (j == 0) 	// first char of pattern
				return  i;
			else
			{
				j--;  i--;	//  go left
			}
		else		//  no match – find char in pattern
		{
			lastch = find(P, S[i]);
			if  (lastch == -1) 	// not found
				i = i + m;		// jump over
			else
				i = i + j – lastch;	// align char
			j = m – 1;	// restart from right
		}
	return  -1;	//  not matched
}

int  find(char P[ ], char  ch)‏
{
	int m, i;  m = length(P);
	for  (i = m – 2; i >= 0; i--)‏
	{
		if  (ch == P[i])‏
		{
			return  i;
		}
	}
	return  -1;
}

This Boyer-Moore algorithm is more efficient for matching of long patterns on textual data.
Both the brute-force and Boyer-Moore algorithms repeat previously matched prefixes. Thus, in the above examples, the prefix “ab” also occurs later in the pattern, P. So far, this information has not been used.