-
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.
-
November 20th, 2008, 12:06 AM
#2
Re: Boyer-Moore string search help
What are the actual values of each of the variables when that line is executed???
This is just a simple case of needing to use the debugger.....
TheCPUWizard is a registered trademark, all rights reserved. (If this post was helpful, please RATE it!)
2008, 2009,2010
In theory, there is no difference between theory and practice; in practice there is.
* Join the fight, refuse to respond to posts that contain code outside of [code] ... [/code] tags. See here for instructions
* How NOT to post a question here
* Of course you read this carefully before you posted
* Need homework help? Read this first
-
November 20th, 2008, 12:43 PM
#3
Re: Boyer-Moore string search help
The Wikipedia article on Boyer-Moore shows workable C-style code: "Boyer–Moore string search algorithm" at http://en.wikipedia.org/wiki/Boyer_moore
In addition, there is a fine collection of string searching algorithms, including Boyer-Moore, and including explanations, at this site: "Exact String Matching Algorithms" at http://www-igm.univ-mlv.fr/~lecroq/string/index.html
The site explains each algorithm, gives pseudo-code, and provides java animations of examples of the algorithm's progress.
You should be able to figure out a good implementation of your "Last()" function from these resources.
Mike
-
November 21st, 2008, 03:17 PM
#4
Re: Boyer-Moore string search help
Thanks all,
I actually came up with this:
Code:
Private Function Last(ByVal charCurrentValue As Char, ByVal arrSearchArray() As Char) As Integer
Dim intSrchSize As Integer = arrSearchArray.Length
Dim i As Integer = intSrchSize - 1
While i <> 0
If charCurrentValue = arrSearchArray(i) Then
Return i
End If
'Exit Function
i -= 1
End While
Return -1
End Function
-
July 2nd, 2013, 12:24 PM
#5
Re: Boyer-Moore string search help
Hey, can you post your final code?
Originally Posted by HawkeyeD
Thanks all,
I actually came up with this:
Code:
Private Function Last(ByVal charCurrentValue As Char, ByVal arrSearchArray() As Char) As Integer
Dim intSrchSize As Integer = arrSearchArray.Length
Dim i As Integer = intSrchSize - 1
While i <> 0
If charCurrentValue = arrSearchArray(i) Then
Return i
End If
'Exit Function
i -= 1
End While
Return -1
End Function
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
|