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*****/
// string
// vector
/***********************************************/

/*****Please use following namespaces*****/
// std
/*****************************************/

#define MAX 256

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

	return true;
}

static vector<int> Search(string str, string pat) {
	vector<int> retVal;
	int strLen = str.length();
	int patLen = pat.length();
	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.push_back((i - patLen));

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

	if (Compare(countP, countT))
		retVal.push_back(strLen - patLen);

	return retVal;
}
								

Example

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

Output

									value: {1, 5, 6, 10}