Boyer-Moore string search help
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: Boyer-Moore string search help

Hybrid View

  1. #1
    Join Date
    Mar 2007
    Posts
    56

    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.

  2. #2
    Join Date
    Mar 2002
    Location
    NY, USA
    Posts
    12,097

    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
    In theory, there is no difference between theory and paractice; 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

  3. #3
    Join Date
    Nov 2002
    Location
    California
    Posts
    4,553

    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

  4. #4
    Join Date
    Mar 2007
    Posts
    56

    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

  5. #5
    Join Date
    Jul 2013
    Posts
    1

    Re: Boyer-Moore string search help

    Hey, can you post your final code?

    Quote Originally Posted by HawkeyeD View Post
    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center