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 nesecito este codigo en visual.net q ademas contenga un reloj q indique cuanto se demoro en ejecutarse
void preKmp(char *x, int m, int kmpNext[])
{
int i, j;
i = 0;
j = kmpNext[0] = -1;
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];
}
}
}
El ejemplo
Fase de preprocesamiento
La tabla kmpNext
|
