Tarea 2:

Para la tarea 2 teniamos que realizar el algoritmo  Booyer-Moore y Knuth-Morris-Pratt

Booyer Moore

Los pasos sos los siguientes:

1. Se dan las lpongitudes de los tamaños que tendra el texto donde se busca y la lóngitud del patron a buscar.
2. Se manda a generar el texto donde se busca
3. Se manda a generar el patron a buscar
Los dos anteriore son generados con un random con los numeros de las letras de la a hasta la z con el numero que le pertenece a cada una en la tabla ascii. 
4. Ya generado lo anterior mandamos a invertir el patron (con un reversed en python para regresarla)
 5.Se busca las letras que contiene texto que no se encuentren en patron
6. Manda a quitar las letras repetidas (dejando una tabla para los saltos)
7.Comienza a comparar palabra:
      7.1 Se compara de derecha izquierda la palabra patron con el texto 
      7.2 Si el primer elemento que verifica no es igual se realiza un salto de la palabra patron
      7.3 Si el primer elemento es correcto pero alguno de los siguientes incorrecto se cuenta el numero de pasos que dio hasta llegar al incorrecto y se toman como brinco.
      7.4 Si todos son correctos se toma el salto de la letra principal.


Código

	from sys import argv
	import random
	import time
	n=int(argv[1]) #recibe parametros n= longitud de cadena donde se busca
	m=int(argv[2]) #recibe parametros m=longitud de patron a buscar
	def generar(tam): #Funcion para generar patron o texto
	x='' #Variable para guardar el texto o patron a generar
	for i in range(tam):
	l=random.randint(97,122) #random de un numer0 de 97 a 122
	x +=(chr(l)) #agrega letra
	return x
	def reversa(patron): #funcion para voltear palabra (forma reversa)
	re_p=''
	for i in reversed(patron):
	re_p +=i
	return re_p # regresa la palabra ya en reversa
	def agregar(rev_patron,texto):
	d=1
	nueva=texto
	for i in texto:
	if (i in rev_patron):
	pass
	else:
	nueva +=i
	return nueva
	def acomodar_palabra(tabla):
	nueva=''
	for i in tabla:
	if (i in nueva):
	pass
	else:
	nueva +=i
	print nueva
	def boyer_moore(texto,patron): #algoritmo boye-moore
	n=len(texto)
	m=len(patron)
	inicio=time.time()
	intento = 0
	rev_patron=reversa(patron) #manda a poner de reversa la palabra
	tabla=agregar(rev_patron,texto)
	print patron
	print rev_patron
	print texto
	print 'tabla',tabla
	tabla=acomodar_palabra(tabla)
	def main():
	texto=generar(n)
	print texto
	patron = generar(m)
	print patron
	texto ='gcatcgcagagagtatacagtacg'
	patron='gcagagag'
	boyer_moore(texto,patron)
	#knuth_morris(texto,patron)
	main()

view raw info.py hosted with ❤ by GitHub

No lo termine :|