jueves, 21 de febrero de 2013

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:
*****
*****





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

1 comentario:

  1. Pues, falta el BM y tu KMP es un poco extraño y carece preprocesamiento. 2 pts por el código. En el reporte falta lo de complejidad de tiempo y complejidad de espacio. Va un punto por el reporte.

    ResponderEliminar