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.