HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Increase performance of Boyer Moore

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
boyerperformanceincreasemoore

Problem

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.

Solution

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)

Code Snippets

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)

Context

StackExchange Code Review Q#47508, answer score: 2

Revisions (0)

No revisions yet.