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.

									function badCharHeuristic($str, $size, &$badchar)
{
	for ($i = 0; $i < 256; $i++)
		$badchar[$i] = -1;

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

function SearchString($str, $pat) {
	$m = strlen($pat);
	$n = strlen($str);
	$i = 0;

	badCharHeuristic($pat, $m, $badchar);

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

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

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

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

	return $result;
}

Example

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

Output

									0
31