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

									public static int[] SearchString(string A, string B)
{
	List<int> retVal = new List<int>();
	ulong siga = 0;
	ulong sigb = 0;
	ulong Q = 100007;
	ulong D = 256;

	for (int i = 0; i < B.Length; ++i)
	{
		siga = (siga * D + (ulong)A[i]) % Q;
		sigb = (sigb * D + (ulong)B[i]) % Q;
	}

	if (siga == sigb)
		retVal.Add(0);

	ulong pow = 1;

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

	for (int j = 1; j <= A.Length - B.Length; ++j)
	{
		siga = (siga + Q - pow * (ulong)A[j - 1] % Q) % Q;
		siga = (siga * D + (ulong)A[j + B.Length - 1]) % Q;

		if (siga == sigb)
			if (A.Substring(j, B.Length) == B)
				retVal.Add(j);
	}

	return retVal.ToArray();
}
								

Example

									string data = "the quick brown fox jumps over the lazy dog";
int[] value = SearchString(data, "the");
								

Output

									0
31