# 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]. Apr 17, 2014 at 20:11
• one tweak: don't calculate i + j in more than one place Apr 17, 2014 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? Apr 17, 2014 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. Apr 18, 2014 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. ;) Apr 18, 2014 at 2:51

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