/*
Name: Algoritmo KMP
Copyright: Codebotic.blogspot.com
Author: Joel Fernandez
Date: 01/12/12 23:43
Description: implementacion de algoritmo KMP
*/
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXT 1001
#define MAXP 1000
using namespace std;
char Texto[MAXT] ;
char Patron[MAXP] ;
signed int tabla[MAXP] ;
signed int rep ; // numero de veces encontrado !
/*
W -> Patron a buscar
tabla -> tabla Fucion fallo
*/
/************************* Tabla KMP **************************/
void tabla_kmp(char W[] , signed int tabla[])
{
signed int pos = 2 ; // posicion actual donde esta tabla de fallo
int cnd = 0 ; // indice del patron
tabla[0] = -1 ;
tabla[1] = 0 ;
while( pos <= strlen(W)-1 )
{
if( W[pos-1] == W[cnd])
{
cnd = cnd + 1 ;
tabla[pos] = cnd ;
pos = pos + 1 ;
}
else
{
if( cnd > 0 )
{
cnd = cnd + tabla[cnd] ;
}
tabla[pos] = 0 ;
pos = pos + 1 ;
}
}
cout<<"\\n\\n >> Tabla de fallo : \\n\\n\\t\\t" ;
for(int i=0; i<strlen(W); i++)
{
cout<<tabla[i]<<" " ;
} cout<<endl ;
}
/************************* Busqueda por KMP ************************/
/*
S -> Texto
W -> Patron a buscar
*/
void KMP( char S[] , char W[], signed int tabla[] )
{
int m = 0 ; // puntero de examen en S
int i = 0 ; // la posición del caracter actual en W, y avance
int tamS = strlen(S) ;
signed int tamW = strlen(W) ;
if( tamS >= tamW )
{
tabla_kmp(W , tabla); // Tabla de fallo
while( m <= tamS-tamW )
{
if( W[i] == S[m+i] )
{
if( i == tamW-1 )
{
cout<<"\\n\\t Encontrado en : " << m + 1 ;
rep ++ ;
m = m + i - tabla[i] ;
if( i > 0 )
i = tabla[i] ;
}
else
i ++ ;
}
else
{
m = m + i - tabla[i] ;
if( i > 0)
i = tabla[i] ;
}
}
}
}
/*************************** Funcion Principal ***********************/
int main()
{
system("color 0B" );
int n , m ;
float t1 , t2, tiempo ; // variables pata tiempo de busqueda
rep = 0 ;
cout<<endl ;
cout<<"\\t ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ» "<<endl;
cout<<"\\t º ALGORITMO DE KNUTH-MORRIS-PRATT º "<< endl ;
cout<<"\\t º ------------------------------- º "<< endl ;
cout<<"\\t ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍŒ "<<endl<<endl;
cout<<endl<<" Ingrese Texto : \\n\\t\\t " ;
gets(Texto);
cout<<endl<<" Ingrese Patron : \\n\\t\\t " ;
gets(Patron);
t1 = clock();
KMP ( Texto, Patron , tabla) ;
t2 = clock();
tiempo = (t2-t1)/100000 ;
if(rep == 0)
cout<<endl<<" >> Patron no encontrado ..! " ;
else
cout<<endl<<endl<<" >> Numero de ocurrencias : "<< rep ;
cout<<endl<<endl<<" >> Tiempo de busqueda : "<< tiempo ;
system("pause>>null");
}