Anagram Substring Search

This algorithm searches for all the occurrences of pattern and its permutations (or anagrams) in the specified text.

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

									Private Const MAX As Integer = 256

Private Shared Function Compare(arr1 As Char(), arr2 As Char()) As Boolean
	For i As Integer = 0 To MAX - 1
		If arr1(i) <> arr2(i) Then
			Return False
		End If
	Next

	Return True
End Function

Public Shared Function Search(str As String, pat As String) As List(Of Integer)
	Dim retVal As New List(Of Integer)()
	Dim countP As Char() = New Char(MAX - 1) {}
	Dim countT As Char() = New Char(MAX - 1) {}

	For i As Integer = 0 To pat.Length - 1
		countP(AscW(pat(i))) = ChrW(AscW(countP(AscW(pat(i)))) + 1)
		countT(AscW(str(i))) = ChrW(AscW(countT(AscW(str(i)))) + 1)
	Next

	For i As Integer = pat.Length To str.Length - 1
		If Compare(countP, countT) Then
			retVal.Add((i - pat.Length))
		End If

		countT(AscW(str(i))) = ChrW(AscW(countT(AscW(str(i)))) + 1)
		countT(AscW(str(i - pat.Length))) = ChrW(AscW(countT(AscW(str(i - pat.Length)))) - 1)
	Next

	If Compare(countP, countT) Then
		retVal.Add(str.Length - pat.Length)
	End If

	Return retVal
End Function
								

Example

									Dim data As String = "NBACGABCAMACB"
Dim pat As String = "ABC"
Dim value As List(Of Integer) = Search(data, pat)
								

Output

									value: {1, 5, 6, 10}