Tarea #2

For this week, we did a string searching program using an algorithm an check how efficient it is in terms of time.

The algorithm used was Knuth-Morris-Pratt which consists in comparing to the list of words with the word you enter.
 *KMP algorithm searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters. (esto dice la wiki :P)

This is the code that performs to verify the comparison:
*****

	import sys
	import random
	import string
	from time import *
	def k_m_p(word,text):
	x=0 #inicio de la lista
	print 'cadena: %s'%(word)
	print 'texto: %s\n' %(text)
	m=len(word)
	n=len(text)
	cont = 0
	comp=0
	t1=time()
	for i in range(n):
	while(x<n):
	cont+=1
	lista = text[x:x+n] #en el texto desde el inicio hasta x+n
	#print 'si paso aki'
	print lista
	for i, (w,l) in enumerate(zip(word,lista)):
	print '[%d]: %s - %s' %(i,w,l)
	comp +=1 #aumentan las comparaciones
	try:
	if(w == l):
	print 'concuerda con : %d'%(x)
	x +=(n-2)
	break
	if(l!=w):
	x+=1
	print 'no concuerda en %d'%(x)
	break
	except:
	break
	x+=1
	timei=time()
	timef= timei -t1
	print '\n tiempo en recorrer la cadena:'+str(timef)+' segundos'
	#print '\npalabra: %s'%(word)
	#print 'Texto: %s' %(text)
	print'\nlargo de palabra: %d'%(m)
	print 'largo de texto: %d'%(n)
	print 'comparacion: %d'%(comp)
	print 'Intentos : %d'%(cont)
	def main():
	w='samoram'
	t='romaamorramorsamorasmoramorarmor'
	k_m_p(w,t)
	# b_m(w,t)
	if(__name__=="__main__"):
	main()

view raw kmp.py hosted with ❤ by GitHub

*****

reference:
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm