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.

• C#
• VB.Net
• C
• C++
• PHP

									/*****Please include following header files*****/
// string
// vector
/***********************************************/

/*****Please use following namespaces*****/
// std
/*****************************************/

static int Max(int a, int b) {
	return a >= b ? a : b;
}

static void BadCharHeuristic(string str, int size, int* badChar) {
	int i;

	for (i = 0; i < 256; i++)
		badChar[i] = -1;

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

static vector<int> SearchString(string str, string pat) {
	vector<int> retVal;
	int m = pat.length();
	int n = str.length();

	int* badChar = new int[256];

	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)
		{
			retVal.push_back(s);
			s += (s + m < n) ? m - badChar[str[s + m]] : 1;
		}
		else
		{
			s += Max(1, j - badChar[str[s + j]]);
		}
	}

	delete[] badChar;
	
	return retVal;
}
								

Example

									string data = "the quick brown fox jumps over the lazy dog";
vector<int> value = SearchString(data, "the");
								

Output

									0
31