Anagram Substring Search

This algorithm searches for all the occurrences of pattern and its permutations (or anagrams) in the specified text.

									$MAX = 256;

function Compare($arr1, $arr2) {
	global $MAX;
	
	for ($i = 0; $i < $MAX; ++$i)
		if ($arr1[$i] != $arr2[$i])
			return false;

	return true;
}

function Search($str, $pat) {
	global $MAX;
	$retVal = array();
	$strLen = strlen($str);
	$patLen = strlen($pat);
	$countP = array();
	$countT = array();
	
	for ($i = 0; $i < $MAX; ++$i) {
		$countP[$i] = 0;
		$countT[$i] = 0;
	}

	for ($i = 0; $i < $patLen; ++$i) {
		$countP[ord($pat[$i])] = chr(ord($countP[ord($pat[$i])]) + 1);
		$countT[ord($str[$i])] = chr(ord($countT[ord($str[$i])]) + 1);
	}

	for ($i = $patLen; $i < $strLen; ++$i) {
		if (Compare($countP, $countT))
			$retVal[] = ($i - $patLen);

		$countT[ord($str[$i])] = chr(ord($countT[ord($str[$i])]) + 1);
		$countT[ord($str[$i - $patLen])] = chr(ord($countT[ord($str[$i - $patLen])]) - 1);
	}

	if (Compare($countP, $countT))
		$retVal[] = ($strLen - $patLen);

	return $retVal;
}

Example

									$data = "NBACGABCAMACB";
$pat = "ABC";
$value = Search($data, $pat);

Output

									value: {1, 5, 6, 10}