Algoritmo KMP(Knuth Morris Pratt)

Iniciado por delirio, 14 Julio 2011, 07:25 AM

0 Miembros y 1 Visitante están viendo este tema.

delirio

Alguien tiene el Algoritmo.......lo necesito.......quiero para codificarlo en C++....tengo que presentarlo..........alguien ayudenme........plisss........

BlackZeroX

The Dark Shadow is my passion.

leogtz

Cualquier libro de algoritmia en la biblioteca de tu universidad lo contiene. Las bibliotecas no muerden.
Código (perl) [Seleccionar]

(( 1 / 0 )) &> /dev/null || {
echo -e "stderrrrrrrrrrrrrrrrrrr";
}

http://leonardogtzr.wordpress.com/
leogutierrezramirez@gmail.com

0wn3t


#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;
}

:)

Ownet web development
Ownet fanpage