Rabin–Karp Algorithm

Rabin–Karp algorithm (a.k.a Karp–Rabin Algorithm) is a string searching algorithm, that uses hashing to find any one of a set of pattern strings in a text.

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

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

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

	newArr[count] = item;

	return newArr;
}

char* GetSubString(char* str, int index, int count) {
	int strLen = strlen(str);
	int lastIndex = index + count;

	if (index >= 0 && lastIndex > strLen) return "";

	char* subStr = malloc(count + 1);

	for (int i = 0; i < count; i++) {
		subStr[i] = str[index + i];
	}

	subStr[count] = '\0';

	return subStr;
}

int* SearchString(char* A, char* B) {
	int* retVal = malloc(sizeof(int));
	int retValSize = 0;
	unsigned long siga = 0;
	unsigned long sigb = 0;
	unsigned long Q = 100007;
	unsigned long D = 256;
	int ALength = strlen(A);
	int BLength = strlen(B);

	for (int i = 0; i < BLength; ++i)
	{
		siga = (siga * D + (unsigned long)A[i]) % Q;
		sigb = (sigb * D + (unsigned long)B[i]) % Q;
	}

	if (siga == sigb)
		retVal = AddItemInArray(retVal, retValSize++, 0);

	unsigned long pow = 1;

	for (int k = 1; k <= BLength - 1; ++k)
		pow = (pow * D) % Q;

	for (int j = 1; j <= ALength - BLength; ++j)
	{
		siga = (siga + Q - pow * (unsigned long)A[j - 1] % Q) % Q;
		siga = (siga * D + (unsigned long)A[j + BLength - 1]) % Q;

		if (siga == sigb)
			if (strcmp(GetSubString(A, j, BLength), B) == 0)
				retVal = AddItemInArray(retVal, retValSize++, j);
	}

	return retVal;
}
								

Example

									char* data = "the quick brown fox jumps over the lazy dog";
int* value = SearchString(data, "the");
								

Output

									0
31