HOLA, NECESITO EL CODIGO FUENTE DE ESTE ALGORITMO DE BUSQUEDA EN TEXTO PERO EN VISUAL.NET, Y Q ADEMAS AL INICIO Y AL FINAL LLEVE UN TIMER PARA Q ME MUESTRE EL TIEMPO Q SE DEMORO EN EJECUTARSE...
Desplazamiento en el algoritmo de Knuth-Morris-Pratt (borde v de u y c b).
La tabla kmpNextpuede ser computada en O(m) en tiempo y espacio antes de la fase de búsqueda, aplicando el mismo algoritmo de búsqueda al patrón en sí, como sí x = y.
La fase de búsqueda puede ser realizada en un tiempo O(m+n). El algoritmo de Knuth-Morris-Pratt efectua a lo más 2n-1 comparaciones de caracteres del Texto durante la fase de búsqueda. El retardo (maximo número de comparaciones para un solo carácter del Texto) esta acotada por log(m) donde es el número aureo( ).
El código en C
void preKmp(char *x, int m, int kmpNext[])
{
int i, j;
i = 0;
j = kmpNext[0] = -1; 'MI PROBLEMA ES Q NO SE COMO DECLARAR ESTE ARRAY
while (i < m)
{
while (j > -1 && x[i] != x[j])
{
j = kmpNext[j];
}
i++;
j++;
if (x[i] == x[j])
{
kmpNext[i] = kmpNext[j];
}
else
{
kmpNext[i] = j;
{
}
}
void KMP(char *x, int m, char *y, int n)
{
int i, j, kmpNext[XSIZE];
/* Preprocesamiento */
preKmp(x, m, kmpNext);
/* Búsqueda */
i = j = 0;
while (j < n)
{
while (i > -1 && x[i] != y[j])
{
i = kmpNext[i];
}
i++;
j++;
if (i >= m)
{
OUTPUT(j - i);
i = kmpNext[i];
}
}
}
|
