Bitap Algorithm

This is a exact string matching version of bitap algorithm. The bitap algorithm (also known as the shift-or, shift-and or Baeza-Yates–Gonnet algorithm) is an approximate string matching algorithm. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given pattern, where approximate equality is defined in terms of Levenshtein distance — if the substring and pattern are within a given distance k of each other, then the algorithm considers them equal. The algorithm begins by precomputing a set of bitmasks containing one bit for each element of the pattern. Then it is able to do most of the work with bitwise operations, which are extremely fast.

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

									Public Shared Function SearchString(text As String, pattern As String) As Integer
	Dim m As Integer = pattern.Length
	Dim R As Integer
	Dim patternMask As Integer() = New Integer(127) {}
	Dim i As Integer

	If String.IsNullOrEmpty(pattern) Then
		Return 0
	End If
	If m > 31 Then
		Return -1 'Error: The pattern is too long!
	End If

	R = Not 1

	For i = 0 To 127
		patternMask(i) = Not 0
	Next

	For i = 0 To m - 1
		patternMask(Convert.ToInt32(pattern(i))) = patternMask(Convert.ToInt32(pattern(i))) And Not (1 << i)
	Next

	For i = 0 To text.Length - 1
		R = R Or patternMask(Convert.ToInt32(text(i)))
		R <<= 1

		If 0 = (R And (1 << m)) Then
			Return (i - m) + 1
		End If
	Next

	Return -1
End Function
								

Example

									Dim index As Integer = SearchString("The quick brown fox jumps over the lazy dog", "fox")
								

Output

									index: 16