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.
for i,x in enumerate(stringy): ASCIIcharset[ord(x)] = i
. Also, I have doubts about thes1[x] is not s2[y]
. \$\endgroup\$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 return0
. \$\endgroup\$