# 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}