-
November 20th, 2008, 12:02 AM
#1
Boyer-Moore string search help
Ok, I do not like doing this as it is for school and not for my work, but I am really stuck here at the moment.
My prof has me doing an assignment in which I make use of two different search algorithms. The Brute-force and the Boyer-Moore. I am searching a text file for a particular string. I have the brute-force code done and it works beautifully. I am nearly complete my Boyer-Moore code but I am stuck on the very last part. That being where to move the "cursor" (for lack of a better term) to where it needs to search from next.
Here is how my program works:
I import the text file contents into a single dimension char array. I then load the string to search for into a different single dimension char array.
I then call the search algorithm passing in both the text file array and the search array. Here is the code I have so far:
Code:
Private Function BoyerMooreSearch(ByVal arrFileContents() As Char, ByVal arrSearchFor() As Char) As Integer
Dim intFileSize As Long = arrFileContents.Length
Dim intSearchSize As Int16 = arrSearchFor.Length
'initialize and set the search counters (not comparison counters) to be used in the boyer method
'Boyer-Moore searches from the right to left
Dim intFileCount = intSearchSize - 1
Dim intSearchCount = intSearchSize - 1
Do
If arrSearchFor(intSearchCount) = arrFileContents(intFileCount) Then
If intSearchCount = 0 Then 'a match was found
Return intFileCount
Else 'keep searching by decrementing the counters (this moves search to the left
intFileCount -= 1
intSearchCount -= 1
End If
End If
'mismatch occurred. determine the new location to start
'HERE IS WHERE I NEED HELP
'***********************************************************
intFileCount = intFileCount + intFileSize - Math.Min(intSearchCount,1+
'***********************************************************
Loop While intFileCount <= intFileSize - 1
I need to redefine the intFileCount at the end of the loop to determine where I start my search again in the array. I have an algorithm that I am trying to code:
intFileCount =intFileCount + intFileSize – Min (intSearchCount, 1 + Last (arrFileContents (intFileCount), arrSeardhFor))
the last part of this line is where I am stuck. Last(arrFileContents(intFileCount),arrSearchFor) is supposed to return the index location my search was on (arrSearchFor is the array containing the string I am looking for).
Example. If the array was searching at arrFileContents(44) and it got 3 positions in it should return 41 (remember a Boyer-Moore actually searches from the left of a starting point)
I hope someone can help me with this. The assignment is due soon. I know I shouldn't have left it so long, but I hate asking for help directly like this for school. Thanks in advance to all.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|