Título: Algoritmo KMP(Knuth Morris Pratt)
Publicado por: delirio en 14 Julio 2011, 07:25 am
Alguien tiene el Algoritmo.......lo necesito.......quiero para codificarlo en C++....tengo que presentarlo..........alguien ayudenme........plisss........
Título: Re: Algoritmo KMP(Knuth Morris Pratt)
Publicado por: BlackZeroX en 14 Julio 2011, 07:27 am
http://es.wikipedia.org/wiki/Algoritmo_Knuth-Morris-Pratt http://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm http://www.ics.uci.edu/~eppstein/161/kmp/ http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm
Google No muerde... el algoritmo es multilenguaje xD.
Dulces Lunas!¡.
Título: Re: Algoritmo KMP(Knuth Morris Pratt)
Publicado por: leogtz en 14 Julio 2011, 07:30 am
Cualquier libro de algoritmia en la biblioteca de tu universidad lo contiene. Las bibliotecas no muerden.
Título: Re: Algoritmo KMP(Knuth Morris Pratt)
Publicado por: 0wn3t en 22 Julio 2011, 04:50 am
#include <stdio.h> #include <stdlib.h> #include <string.h>
#include "kmp.h"
static int* prefix = NULL; static int max_size = 0;
static void GetPrefixValue(const char* strPattern, int iPatternLen) { if (iPatternLen>max_size) { prefix = (int*)realloc(prefix, iPatternLen*sizeof(int)); max_size = iPatternLen; } int i, j; /* i runs through the string, j counts the hits*/ i = 1; j = 0; prefix[0] = 0; while(i<iPatternLen) { if(strPattern[i] == strPattern[j]) { prefix[i] = ++j; } else { j = 0; prefix[i] = j; } i++; } }
static int KMPStringMatch(const char* strPattern, int iPatternLen, const char* strTarget, int iTargetLen) { int j =0; int i; for (i=0;i<iPatternLen;i++) { while ((strPattern[i] != strTarget[j]) && (j > 0)) j = prefix[j-1]; if (strPattern[i] == strTarget[j]) j++; if (j == iTargetLen) return i - j + 1; } return -1; }
int KMP(const char* strPattern, int len, const char* strTarget) { GetPrefixValue(strPattern, len); return KMPStringMatch(strPattern, len, strTarget, strlen(strTarget)); }
void KMP_end() { free(prefix); prefix=NULL; max_size=0; }
:)
|