Naive implementation of Karp-Rabin pattern matching algorithm

Question

I'm having problem implementing the naive version of Karp-Rabin pattern marcher; I'm not getting the expected result. Here's my example;

string='today is a good day'
sub='good'

I would like to find the pattern good in the string above.

def kapr(n,m):
    for i in range(len(n)-len(m)+1):
        for j in range(len(m)):
            if n[i+j-1]!=m[j]:
                continue
        return i
    return not found

Print (kapr(string, sub)) 

Output=0 Expected output=11, should correspond with the offset of good in the string.

Thanks for your help.

Answer 1

You want break instead of continue. Continue will move on to the next iteration of the inner loop, while break will exit the inner loop. Furthermore, you aren't jumping directly to the next iteration of the outer loop by using break, so you will hit the return i statement. To stop this happening, you can use a for/else branch.

E.g.

for j in range(len(m)):
    if n[i+j-1]!=m[j]:
        break
else:
    return i

It will only return i if the inner loop completes normally.

The index it returns is also not zero indexed, so with the above modifications it will return 12. Should be simple to update if you want it to be zero-indexed!