Boyer–Moore String Search Algorithm

Boyer–Moore string search algorithm is an efficient string searching algorithm that is the standard benchmark for practical string search literature.

									#define NO_OF_CHARS 256

int max(int a, int b) {
	return (a > b) ? a : b;
}

void badCharHeuristic(char *str, int size, int badchar[NO_OF_CHARS])
{
	int i;

	for (i = 0; i < NO_OF_CHARS; i++)
		badchar[i] = -1;

	for (i = 0; i < size; i++)
		badchar[(int)str[i]] = i;
}

int* SearchString(char* str, char* pat) {
	int m = strlen(pat);
	int n = strlen(str);
	int badchar[NO_OF_CHARS];
	int* arr = (int*)malloc(sizeof(int) * n);
	int i = 0;

	badCharHeuristic(pat, m, badchar);

	int s = 0;
	while (s <= (n - m))
	{
		int j = m - 1;

		while (j >= 0 && pat[j] == str[s + j])
			j--;

		if (j < 0)
		{
			arr[i++] = s;
			s += (s + m < n) ? m - badchar[str[s + m]] : 1;
		}
		else
			s += max(1, j - badchar[str[s + j]]);
	}

	int* result = (int*)malloc(sizeof(int) * i);

	for (int j = 0; j < i; j++)
	{
		result[j] = arr[j];
	}

	return result;
}

Example

									char* data = "the quick brown fox jumps over the lazy dog";
int* value = SearchString(data, "the");

Output

									0
31