Anagram Substring Search

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



									private const int MAX = 256;

private static bool Compare(char[] arr1, char[] arr2)
{
	for (int i = 0; i < MAX; ++i)
		if (arr1[i] != arr2[i])
			return false;

	return true;
}

public static List<int> Search(string str, string pat)
{
	List<int> retVal = new List<int>();
	char[] countP = new char[MAX];
	char[] countT = new char[MAX];

	for (int i = 0; i < pat.Length; ++i)
	{
		(countP[pat[i]])++;
		(countT[str[i]])++;
	}

	for (int i = pat.Length; i < str.Length; ++i)
	{
		if (Compare(countP, countT))
			retVal.Add((i - pat.Length));

		(countT[str[i]])++;
		countT[str[i - pat.Length]]--;
	}

	if (Compare(countP, countT))
		retVal.Add(str.Length - pat.Length);

	return retVal;
}
								


Example

									string data = "NBACGABCAMACB";
string pat = "ABC";
List<int> value = Search(data, pat);
								


Output

									value: {1, 5, 6, 10}