Anagram Substring Search

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

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

									/*****Please include following header files*****/
// stdlib.h
// string.h
/***********************************************/

#define MAX 256

int* AddItemInArray(int* arr, int count, int item) {
	int* newArr = (int*)malloc(sizeof(int) * (count + 1));

	for (int i = 0; i < count; ++i) {
		newArr[i] = arr[i];
	}

	newArr[count] = item;

	return newArr;
}

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

	return true;
}

int Search(char* str, char* pat, int** retVal) {
	int retValCount = 0;
	int strLen = strlen(str);
	int patLen = strlen(pat);
	char countP[MAX] = { 0 };
	char countT[MAX] = { 0 };

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

	for (int i = patLen; i < strLen; ++i) {
		if (Compare(countP, countT))
			*retVal = AddItemInArray(*retVal, retValCount++, (i - patLen));

		(countT[str[i]])++;
		countT[str[i - patLen]]--;
	}

	if (Compare(countP, countT))
		*retVal = AddItemInArray(*retVal, retValCount++, (strLen - patLen));

	return retValCount;
}
								

Example

									char* data = "NBACGABCAMACB";
char* pat = "ABC";
int* value = (int*)malloc(sizeof(int));
int count = Search(data, pat, &value);
								

Output

									value: {1, 5, 6, 10}