Boyer–Moore String Search Algorithm

Boyer–Moore string search algorithm is an efficient string searching algorithm that is the standard benchmark for practical string search literature.

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

									Public Shared Function SearchString(str As String, pat As String) As Integer()
	Dim retVal As New List(Of Integer)()
	Dim m As Integer = pat.Length
	Dim n As Integer = str.Length

	Dim badChar As Integer() = New Integer(255) {}

	BadCharHeuristic(pat, m, badChar)

	Dim s As Integer = 0
	While s <= (n - m)
		Dim j As Integer = m - 1

		While j >= 0 AndAlso pat(j) = str(s + j)
			j -= 1
		End While

		If j < 0 Then
			retVal.Add(s)
			s += If((s + m < n), m - badChar(AscW(str(s + m))), 1)
		Else
			s += Math.Max(1, j - badChar(AscW(str(s + j))))
		End If
	End While

	Return retVal.ToArray()
End Function

Private Shared Sub BadCharHeuristic(str As String, size As Integer, ByRef badChar As Integer())
	Dim i As Integer

	For i = 0 To 255
		badChar(i) = -1
	Next

	For i = 0 To size - 1
		badChar(AscW(str(i))) = i
	Next
End Sub
								

Example

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

Output

									0
31