I do not work with the Horspool algorithm

0

I've been replicating the Horspool algorithm in Python that I found in a book.

I have already made the ShifTable and the HorspoolMarching. The problem is that I can not find the match or the index, that is, it returns -1 and I do not know the reason.

I enclose the theoretical algorithm.

ShifTable

HorspoolMarching

I also attach the code that I have. Test.py

'''
Created on 26/05/2018

@author: None
'''
def shifTable(patron):
    m = len(patron)
    tabla = []
    for i in range(0, 255):
        tabla.append(m)
    for j in range(0, m - 2):
        tabla[ord(patron[j])] = m - 1 - j
    return tabla


def horspoolMarching2(patron, texto):
    m = len(patron)
    n = len(texto)

    tabla = shifTable(patron)
    print(tabla)

    i = m - 1
    while i <= (n - 1):
        k = 0
        while (k <= (m - 1)) and (patron[m - 1 - k] == texto[i + k]):
            k = k + 1
        if k == m:
            return (i - m + 1)
        else:
            i = i + tabla[ord(texto[i])]
    return -1


if __name__ == '__main__':
    texto = "JIM_SA W_ME_IN_A_BARBERSHOP"
    patron = "BARBER"
    print(horspoolMarching2(patron, texto))

I can not find the reason why it does not work. I return -1 and should not give that result.

    
asked by prog2 27.05.2018 в 02:58
source

0 answers