Octavo Semestre: STRING MATCHING

For this homework we had to implement two algorithms for matching strings. These are Boyer-Moore algorithm and Knuth-Morris-Pratt algorithm. You can find a good and brief explanation along with C pseudocode of Boyer-Moore here, and here for Knuth-Morris-Prat.

Here's my implementation of the Boyer algorithm . It is unfinished.

	from sys import argv

	def generar(Texto,Patron):
	#Se genera el patron en reversa
	#que usaremos para la tabla de saltos
	copia = list(Patron)
	bad_char=copia
	bad_char.reverse()

	#Se agregam los caracteres del texto
	#que no aparecen en el patron
	for i in Texto:
	if i not in bad_char:
	bad_char.append(i)

	#Se crea un diccionario para la tabla de saltos
	tabla_saltos = {}
	for i in range(len(bad_char)):
	tabla_saltos[bad_char[i]]= i

	return tabla_saltos


	def algoritmo(Texto,Patron):
	global tabla_saltos
	#Cuando no se usa la tabla de saltos
	#se necesita usar el contador
	contador = 0
	inicio = 0
	final = len(Patron)-1
	lugar = final
	predesesor = inicio

	while (final <= len(Texto)-1):
	predesesor = inicio
	#Comparamos de derecha a izquierda
	if Texto[final]!=Patron[lugar]:
	print "mal desde el inicio"

	#Buscamos en el diccionario
	#el valor de la letra donde estamos posicionados

	mov = tabla_saltos[Texto[final]]
	inicio = inicio + mov
	final = final + mov
	lugar = len(Patron)-1
	else:
	contador+=1
	lugar = 0
	#for i in range(len(Patron)-1):
	while inicio <= len(Patron)-2:
	contador+=1
	#Si la posicion inicial hacia match,
	#continuamos comparando
	if Texto[lugar]==Patron[inicio]:
	lugar+=1
	inicio+=1
	if inicio > len(Patron)-2:
	print "Match"
	predesesor = predesesor + 1
	final = predesesor + len(Patron)-1
	pass
	else:
	mov = contador
	predesesor = predesesor + mov
	final = predesesor + len(Patron)-1
	break
	break



	Texto = list(argv[1])
	Patron = list(argv[2])

	tabla_saltos = generar(Texto,Patron)
	algoritmo(Texto,Patron)
	#comparar(Texto,Patron)