4
\$\begingroup\$

Here is my Boyer Moore code in Python:

def BoyerMoore(stringy, substring):
    if stringy == substring:
        return 0
    ASCIIcharset = [-1]*256
    for x in xrange(len(stringy)):
        ASCIIcharset[ord(stringy[x])] = x

    stringLen = len(stringy)
    substringLen = len(substring)
    for i in xrange(stringLen - substringLen):
        skip = 0
        for j in xrange(substringLen - 1 , 0, -1):
            if stringy[i + j] is not substring[j]:
                skip = max(1, j - ASCIIcharset[ord(stringy[i + j])])
                i += skip
                break
        if skip == 0:
            return i
    return -1

I was wondering what are some small tweaks here and there that I can do to increase the efficiency. Redesigning this code is fine too.

Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ No time for a proper review atm but the pythonic way to write your first loop is : for i,x in enumerate(stringy): ASCIIcharset[ord(x)] = i. Also, I have doubts about the s1[x] is not s2[y]. \$\endgroup\$
    – SylvainD
    Apr 17 '14 at 20:11
  • \$\begingroup\$ one tweak: don't calculate i + j in more than one place \$\endgroup\$
    – jcfollower
    Apr 17 '14 at 20:48
  • 1
    \$\begingroup\$ Are you sure your skip calculation is right? For example, if you are on the letter 'a', then ASCIIcharset[ord('a')] will have the highest index where 'a' appears in stringy. Won't this frequently be greater than j? In that case, does it save you any time to calculate and use skip? \$\endgroup\$
    – jcfollower
    Apr 17 '14 at 20:51
  • \$\begingroup\$ Shouldn't ASCIIcharset be based on the needle instead of the haystack? Otherwise you'll skip too far ahead, e.g., BoyerMoore('foo is not a foo', 'foo') should return 0. \$\endgroup\$
    – David Harkness
    Apr 18 '14 at 2:49
  • \$\begingroup\$ I would prefer the needle to proceed the haystack. I don't recall Python's preference, but please ignore PHP's dysfunctional use of both. ;) \$\endgroup\$
    – David Harkness
    Apr 18 '14 at 2:51
2
\$\begingroup\$

The following examples show that there is something wrong in your code :

print(BoyerMoore('azertyuiop', 'zertyuio' ))  #  1 - fair enough
print(BoyerMoore( 'zertyuio' , 'azertyuiop')) # -1 - so far so good
print(BoyerMoore('azertyuiop', 'azertyuiop')) #  0 - ok
print(BoyerMoore('abcdefgiop', 'iop'))        # -1 - looks wrong to me
print(BoyerMoore('iop'       , 'abcdefgiop')) # -1 - ok (just wanted to check that arguments were in the right order)
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.