Python: Rabin-Karp algorithm

Question

I use the Rabin-Karp algorithm for fun. I came across this pseudo code:

    RABIN -KARP -MATCHER (T, P, d, q)
    1 n = T.length
    2 m = P.length
    3 h = d^(m-1) mod q
    4 p=0
    5 t= 0
    6 for i = 1 to m
    / preprocessing
    /
    7 p = (dp + P [i]) mod q
    8 t = (dt + T [i]) mod q
    9 for s = 0 to n-m
    / matching
    /
    10     if p == t
    11         if P [1... m] == T [s + 1...s + m]
    12             print "Pattern occurs with shift" s
    13     if s < n-m
    14         t  = (d(t-T[s + 1]h) + T [s + m + 1]) mod q

I implemented in Python 2.7 like this:

def Rabin_Karp_Matcher(text, pattern, d, q):
    n = len(text)
    m = len(pattern)
    h = pow(d,m-1)%q
    p = 0
    t =0
    result = []
    for i in range(m): # preprocessing
        p = (d*p+ord(pattern[i]))%q
        t = (d*t+ord(text[i]))%q
    for s in range(n-m):
        if p == t: # check character by character
            match = True
            for i in range(m):
                if pattern[i] != text[s+i]:
                    match = False
                    break
            if match:
                result = result + [s]
        if s < n-m:
                t = (d*(t-ord(text[s+1])*h)+ord(text[s+m]))%q #index out of bounds here
    return result

where result is a list containing the index in the text of the template.

My code does not find 26 in 3141592653589793 and I suspect this has something to do with my hash code defined by line 14 of the pseudocode. Anyone can help with this.

I went through the following parameters:

P = "26" T = "3141592653589793" d = 257 q = 11

P and T must be strings / arrays of characters

Answer 1

Here is the working version of your code:

def Rabin_Karp_Matcher(text, pattern, d, q):
    n = len(text)
    m = len(pattern)
    h = pow(d,m-1)%q
    p = 0
    t = 0
    result = []
    for i in range(m): # preprocessing
        p = (d*p+ord(pattern[i]))%q
        t = (d*t+ord(text[i]))%q
    for s in range(n-m+1): # note the +1
        if p == t: # check character by character
            match = True
            for i in range(m):
                if pattern[i] != text[s+i]:
                    match = False
                    break
            if match:
                result = result + [s]
        if s < n-m:
            t = (t-h*ord(text[s]))%q # remove letter s
            t = (t*d+ord(text[s+m]))%q # add letter s+m
            t = (t+q)%q # make sure that t >= 0
    return result
print (Rabin_Karp_Matcher ("3141592653589793", "26", 257, 11))
print (Rabin_Karp_Matcher ("xxxxx", "xx", 40999999, 999999937))

Output:

[6]
[0, 1, 2, 3]

, text[0..m] == pattern. , text[1..m+1] == pattern. , text[0] ( h): t = (t-h*ord(text[s]))%q. text[m] : t = (t*d+ord(text[s+m]))%q. text[1] text[m+1] .. t = (t+q)%q , q (-q; 0], , [0; q).

, n-m+1, n-m, - for s in range(n-m+1). ( "xx" "xxxxx" ).

:

• h = pow(d,m-1)%q , m . q m-2.

• O (nm) . text="a"*100000 pattern="a"*50000 50001 , , -. , , (.. , ). q .

Answer 2

, , " s":

def Rabin_Karp_Matcher(text, pattern, d, q):
    n = len(text)
    m = len(pattern)
    h = pow(d,m-1)%q
    p = 0
    t =0
    result = []
    for i in range(m): # preprocessing
        p = (d*p+ord(pattern[i]))%q
        t = (d*t+ord(text[i]))%q

        for s in range(n-m):
            if p == t: # check character by character
                match = True
                for i in range(m):
                    if pattern[i] != text[s+i]:
                        match = False
                        break
                if match:
                    result = result + [s]
            if s < n-m:
                    t = (d*(t-ord(text[s+1])*h)+ord(text[s+m]))%q #index out of bounds here


    return result

6, , , . .