# Increase performance of Boyer Moore

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.

• 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]. – SylvainD Apr 17 '14 at 20:11
• one tweak: don't calculate i + j in more than one place – jcfollower Apr 17 '14 at 20:48
• 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? – jcfollower Apr 17 '14 at 20:51
• 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. – David Harkness Apr 18 '14 at 2:49
• 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. ;) – David Harkness Apr 18 '14 at 2:51

print(BoyerMoore('azertyuiop', 'zertyuio' ))  #  1 - fair enough