This isn't for a class is it?
It seems pretty simple, looking at the algorithm for the first time. It
currently starts m (the length of the pattern) characters into the buffer,
you want to start m characters from the end. You need to search forward
through the pattern rather than backward. The trick is figuring out the new
distance array (you need distance to the beginning not the distance to the
end) and the outer loop (decrement i instead of increment). Oh, and
searching forward through the pattern will change the if at the end.
One other note, you might want to take advantage of short-circuiting a
little. If you fail the first test and the flag is true, then you'll perform
both the next tests (which each include 2 tests), but there's no reason to
do either.
if (test1 || (test2 && !flag) || (test3 && !flag))
becomes
if (test1 || (!flag && (test2 || test3)))
Now if you fail test1 and the flag is true (!flag evaluates to false), you
don't do test2 or test3.
David
> -----Original Message-----
> From: Robert Welz [mailto:email@hidden]
> Sent: Thursday, April 25, 2002 5:15 AM
> To: Jonah Petri
> Cc: email@hidden
> Subject: Antw: Boyle Moore algorithm
>
>
> Hello.
> Yeah, it works great!
>
> Now I should implement the Boye Moore algorithm for backward
> searching. Has someone done this before and can help?
>
> Greetings,
> Robert
>
> Am Mittwoch, 24. April 2002 schrieb Jonah Petri <email@hidden>:
> >A good way to do case insensitivity is to make sure all the
> characters
> >you read are lowercase, and if they aren't, to make them so.
> Basically
> >take each char you read and do:
> >
> >if (theChar >= 'A' && theChar <='Z') //If theChar is upper case
> >{
> > theChar -= 'A' - 'a'; //Change to lowercase
> >}
> >
> >Make sure to do that to all of your inputs, including your search
> >string. This is better than saying "if it isn't lowercase,
> (>= 'a' and
> ><='z') then subtract 'A' - 'a' from it," because it won't translate
> >non-letter characters. I got bit by that once, so just beware.
> >
> >-Jonah
> >
> >On Wednesday, April 24, 2002, at 08:17 AM, Robert Welz wrote:
> >
> >> Buh ,
> >> I even cannot get this algorithm get to work with case
> insensitivity.
> >>
> >> Any help welcome!!!
> >>
> >> Robert
> >>
> >> Am Dienstag, 23. April 2002 schrieb Robert Welz
> <email@hidden>:
> >>> Hello.
> >>> I have code for the Boyle - Moore Algorithm which is a fast
> >>> approach to find small Strings in huge texts. It works forward
> >>> but I want to implement a "Find backward" control. Can someone
> >>> help? I cannot get it run backward", maybe someone has it done
> >>> already.
> >>>
> >>> Thanks for help,
> >>> Robert
> >>>
> >>> UInt32 bm_search (unsigned char *buffer, long length,
> unsigned char
> >>> *pattern, Boolean flag)
> >>> {
> >>> // 19.4.2002 Robert : return value was unsigned char*,
> is now UInt32
> >>>
> >>> Str255 patternCaps;
> >>> Str255 patternNoCaps;
> >>> short iErr;
> >>>
> >>>
> >>>
> >>> register int i, j, k, m, n;
> >>>
> >>> m = strlen ((char const *)pattern);
> >>> n = length;
> >>>
> >>>
> >>> if (m > n)
> // match is impossible!
> >>> return -1;
> >>>
> >>>
> >>> if (!flag)
> >>> {
> >>> // LowerText ((char *)buffer, n);
> // convert to lower case
> >>> // LowerText ((char *)pattern, m);
> >>> // new: LowercaseText( Ptr textPtr, short len,
> ScriptCode script);
> >>>
> >>> memcpy((StringPtr)patternNoCaps, pattern, m);
> >>> memcpy((StringPtr)patternCaps, pattern, m);
> >>> LowercaseText ( (char *)patternNoCaps, m,
> smCurrentScript );
> >>> UppercaseText ( (char *)patternCaps, m,
> smCurrentScript );
> >>> }
> >>>
> >>> // build distance array:
> >>>
> >>> for (i = 0; i < 256; distance[i++] = m) // fill with maxlen
> >>> ;
> >>> for (i = 0; i < m - 1; i++)
> >>> distance[pattern[i]] = m - i - 1;
> >>>
> >>> i = m;
> >>>
> >>> do
> >>> {
> >>> j = m;
> >>> k = i;
> >>> do
> >>> {
> >>> k--; j--;
> >>> }
> >>> while ((j >= 0) && ( (buffer[k] == pattern[j]) || ((
> >>> buffer[k] == patternNoCaps[j]) && !flag ) || (( buffer[k] ==
> >>> patternCaps[j]) && !flag ) ));
> >>> i += distance[buffer[i - 1]];
> >>> }
> >>> while (j >= 0 && i <= n);
> >>> if (j < 0)
> >>> return k + 1 ;
> >>> return -1;
> >>> }
> >>>
> >>>
> //////////////////////////////////////////////////////////////
> //////////
> >>> ////////
> >>> //
> >>> // Boyer-Moore search algorithm
> >>> //
> >>> // buffer = char pointer to source data
> >>> // length = bytes in buffer
> >>> // pattern = null-terminated search string
> >>> // flag = if true search is case sensitiv
> >>> // if false ignore case
> >>> //
> >>> // return value:
> >>> // selStart begin of matched string
> >>> // //pointer to matched
> string if found
> >>> // -1 if not found
> >>> // nil if not found
> >>> //
> >>> // Limits:
> >>> // length must not exceed 32k!
> >>> // uses script manager for
> case conversion!
> >>> //
> >>>
> //////////////////////////////////////////////////////////////
> //////////
> >>> ////////
> >>>
> >>>
> /*------------------------------------------------------------
> ------------------
> >>> #
> >>> # String Search Application
> >>> #
> >>> #
> >>> # Boyer-Moore.c - C Source
> >>> #
> >>> # Copyright ) Linotype-Hell AG 1992-96
> >>> # All rights reserved.
> >>> #
> >>> # Versions:
> >>> #
> >>> # Components:
> >>> #
> >>> #
> >>> #
> >>>
> --------------------------------------------------------------
> ----------------*
> >>> /
> >>> _______________________________________________
> >>> studentdev mailing list | email@hidden
> >>> Help/Unsubscribe/Archives:
> >>> http://www.lists.apple.com/mailman/listinfo/studentdev
> >>> Do not post admin requests to the list. They will be ignored.
> >> _______________________________________________
> >> studentdev mailing list | email@hidden
> >> Help/Unsubscribe/Archives:
> >> http://www.lists.apple.com/mailman/listinfo/studentdev
> >> Do not post admin requests to the list. They will be ignored.
> _______________________________________________
> studentdev mailing list | email@hidden
> Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/studentdev
Do not post admin requests to the list. They will be ignored.
_______________________________________________
studentdev mailing list | email@hidden
Help/Unsubscribe/Archives: http://www.lists.apple.com/mailman/listinfo/studentdev
Do not post admin requests to the list. They will be ignored.
