document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. /*
  2.  
  3.   Name: Algoritmo KMP
  4.  
  5.   Copyright: Codebotic.blogspot.com
  6.   Author:   Joel Fernandez
  7.   Date: 01/12/12 23:43
  8.   Description: implementacion de algoritmo KMP
  9. */
  10.  
  11. #include<iostream>
  12. #include<string.h>
  13. #include<stdio.h>
  14. #include<stdlib.h>
  15. #include<time.h>
  16. #define MAXT 1001
  17. #define MAXP 1000
  18. using namespace std;
  19.  
  20. char        Texto[MAXT] ;
  21. char        Patron[MAXP] ;
  22. signed int  tabla[MAXP]  ;
  23. signed int  rep  ;            // numero de veces encontrado !
  24.  
  25.  
  26. /*
  27.     W -> Patron  a buscar
  28.     tabla -> tabla Fucion fallo
  29. */
  30.  
  31. /************************* Tabla KMP **************************/
  32.  
  33. void tabla_kmp(char W[] ,  signed int tabla[])
  34. {
  35.      signed int pos  = 2 ;  // posicion actual donde esta tabla de fallo
  36.      int        cnd  = 0 ;  // indice del patron
  37.  
  38.      tabla[0] = -1 ;
  39.      tabla[1] = 0 ;
  40.  
  41.  
  42.      while( pos <= strlen(W)-1 )
  43.      {
  44.            if( W[pos-1] == W[cnd])
  45.            {
  46.                  cnd = cnd + 1 ;
  47.                  tabla[pos] = cnd ;
  48.                  pos = pos + 1 ;
  49.            }
  50.            else
  51.            {
  52.                  if( cnd > 0 )
  53.                  {
  54.                      cnd = cnd + tabla[cnd] ;
  55.                  }
  56.  
  57.                  tabla[pos] = 0 ;
  58.                  pos = pos + 1 ;
  59.  
  60.            }
  61.  
  62.      }
  63.  
  64.      cout<<"\\n\\n  >> Tabla de fallo : \\n\\n\\t\\t" ;
  65.  
  66.      for(int i=0; i<strlen(W); i++)
  67.      {
  68.             cout<<tabla[i]<<"  " ;
  69.      } cout<<endl ;
  70. }
  71.  
  72. /************************* Busqueda por KMP ************************/
  73.  
  74. /*
  75.     S -> Texto
  76.     W -> Patron  a buscar
  77. */
  78.  
  79. void KMP( char S[] , char W[], signed int tabla[] )
  80. {
  81.       int         m = 0 ;     // puntero de examen en S
  82.       int         i = 0 ;     // la posición del caracter actual en W, y avance
  83.  
  84.       int         tamS  = strlen(S) ;
  85.       signed int  tamW = strlen(W) ;
  86.  
  87.       if( tamS >= tamW )
  88.       {
  89.           tabla_kmp(W , tabla);  //  Tabla de fallo
  90.  
  91.           while( m <= tamS-tamW )
  92.           {
  93.                 if( W[i] == S[m+i] )
  94.                 {
  95.                      if( i == tamW-1 )
  96.                      {
  97.                           cout<<"\\n\\t Encontrado en : " << m + 1 ;
  98.  
  99.                           rep ++ ;
  100.  
  101.                           m  = m + i - tabla[i] ;
  102.  
  103.                           if( i > 0 )
  104.                              i = tabla[i] ;
  105.                      }
  106.                      else
  107.                           i ++ ;
  108.  
  109.                 }
  110.                 else
  111.                 {
  112.                     m = m + i - tabla[i] ;
  113.  
  114.                     if( i > 0)
  115.                         i = tabla[i] ;
  116.  
  117.                 }
  118.  
  119.           }
  120.  
  121.       }
  122.  
  123. }
  124.  
  125.  
  126. /*************************** Funcion Principal ***********************/
  127.  
  128. int main()
  129. {
  130.     system("color 0B" );
  131.  
  132.     int n , m ;
  133.     float t1 , t2, tiempo ;  // variables pata tiempo de busqueda
  134.     rep = 0 ;
  135.  
  136.     cout<<endl ;
  137.     cout<<"\\t     ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ» "<<endl;
  138.     cout<<"\\t     º          ALGORITMO DE KNUTH-MORRIS-PRATT            º "<< endl ;
  139.     cout<<"\\t     º          -------------------------------            º "<< endl ;
  140.     cout<<"\\t     ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍŒ "<<endl<<endl;
  141.  
  142.  
  143.     cout<<endl<<" Ingrese Texto :  \\n\\t\\t " ;
  144.     gets(Texto);
  145.  
  146.     cout<<endl<<" Ingrese Patron :  \\n\\t\\t " ;
  147.     gets(Patron);
  148.  
  149.     t1 = clock();
  150.  
  151.     KMP ( Texto,  Patron , tabla) ;
  152.  
  153.     t2 = clock();
  154.  
  155.     tiempo = (t2-t1)/100000 ;
  156.  
  157.     if(rep  == 0)
  158.         cout<<endl<<"  >> Patron no encontrado ..!  " ;
  159.     else
  160.         cout<<endl<<endl<<"  >> Numero de ocurrencias : "<< rep ;
  161.  
  162.     cout<<endl<<endl<<"  >> Tiempo de busqueda : "<< tiempo ;
  163.  
  164.  
  165.  
  166.     system("pause>>null");
  167. }
');