Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- 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");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement