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
        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.

  • \$\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
    Commented Apr 17, 2014 at 20:11
  • \$\begingroup\$ one tweak: don't calculate i + j in more than one place \$\endgroup\$
    – jcfollower
    Commented Apr 17, 2014 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
    Commented Apr 17, 2014 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\$ Commented Apr 18, 2014 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\$ Commented Apr 18, 2014 at 2:51

1 Answer 1


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)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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