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 Shared Function SearchString(A As String, B As String) As Integer()
	Dim retVal As New List(Of Integer)()
	Dim siga As ULong = 0
	Dim sigb As ULong = 0
	Dim Q As ULong = 100007
	Dim D As ULong = 256

	For i As Integer = 0 To B.Length - 1
		siga = (siga * D + CULng(AscW(A(i)))) Mod Q
		sigb = (sigb * D + CULng(AscW(B(i)))) Mod Q
	Next

	If siga = sigb Then
		retVal.Add(0)
	End If

	Dim pow As ULong = 1

	For k As Integer = 1 To B.Length - 1
		pow = (pow * D) Mod Q
	Next

	For j As Integer = 1 To A.Length - B.Length
		siga = (siga + Q - pow * CULng(AscW(A(j - 1))) Mod Q) Mod Q
		siga = (siga * D + CULng(AscW(A(j + B.Length - 1)))) Mod Q

		If siga = sigb Then
			If A.Substring(j, B.Length) = B Then
				retVal.Add(j)
			End If
		End If
	Next

	Return retVal.ToArray()
End Function
								

Example

									Dim data = "the quick brown fox jumps over the lazy dog"
Dim value = SearchString(data, "the")
								

Output

									0
31