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

									/*****Please include following header files*****/
// string
// vector
/***********************************************/

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

static vector<int> SearchString(string A, string B) {
	vector<int> retVal;
	unsigned long siga = 0;
	unsigned long sigb = 0;
	unsigned long Q = 100007;
	unsigned long D = 256;
	int ALength = A.length();
	int BLength = B.length();

	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.push_back(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 (A.substr(j, BLength) == B)
				retVal.push_back(j);
	}

	return retVal;
}
								

Example

									string data = "the quick brown fox jumps over the lazy dog";
vector<int> value = SearchString(data, "the");
								

Output

									0
31