home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 79 / IOPROG_79.ISO / soft / Codice / sm1.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2004-02-26  |  2.1 KB  |  102 lines
  1. #include <iostream.h>
  2. #include <conio.h>
  3.  
  4. void ForzaBruta(char *x, int m, char *y, int n) {
  5.    int i, j;
  6.  
  7.    /* Ricerca di forza bruta */
  8.    for (j = 0; j <= n - m; ++j) {
  9.       for (i = 0; i < m && x[i] == y[i + j]; ++i);
  10.       if (i >= m)
  11.          cout<<j<<"\n";
  12.    }
  13. }
  14.  
  15. #define EOS '\0'
  16.    
  17. void ForzaBruta2(char *x, int m, char *y, int n) { 
  18.   char *yb; 
  19.   /* Ricerca di Forza Bruta migliorato */ 
  20.   for (yb = y; *y != EOS; ++y) 
  21.     if (memcmp(x, y, m) == 0) 
  22.       cout<<(y - yb)<<"\n";
  23. }
  24.  
  25. #define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))
  26.  
  27. void KarpRabin(char *x, int m, char *y, int n) {
  28.    int d, hx, hy, i, j;
  29.  
  30.    /* Pre-elaborazione */
  31.    /* numero di computazioni d = 2^(m-1) 
  32.       con operatore di shift sinistro */
  33.    for (d = i = 1; i < m; ++i)
  34.       d = (d<<1);
  35.  
  36.    for (hy = hx = i = 0; i < m; ++i) {
  37.       hx = ((hx<<1) + x[i]);
  38.       hy = ((hy<<1) + y[i]);
  39.    }
  40.    //cout<<"hx : "<<hx<<"\n\n";
  41.    
  42.    /* Ricerca di Karp Rabin */
  43.    j = 0;
  44.    while (j <= n-m) {    
  45.       //cout<<"hy("<<j<<"): "<<hy<<"\n";
  46.       if (hx == hy && memcmp(x, y + j, m) == 0)
  47.          cout<<j<<"\n";
  48.       hy = REHASH(y[j], y[j + m], hy);
  49.       
  50.       ++j;
  51.    }
  52. }
  53.  
  54. void preMorrisPratt(char *x, int m, int mpNext[]) {
  55.    int i, j;
  56.  
  57.    i = 0;
  58.    j = mpNext[0] = -1;
  59.    while (i < m) {
  60.       while (j > -1 && x[i] != x[j])
  61.          j = mpNext[j];
  62.       mpNext[++i] = ++j;
  63.    }
  64. }
  65.  
  66.  
  67. void MorrisPratt(char *x, int m, char *y, int n) {
  68.    int i, j, mpNext[5];
  69.  
  70.    /* Pre-elaborazione*/
  71.    preMorrisPratt(x, m, mpNext);
  72.  
  73.    /* Ricerca */
  74.    i = j = 0;
  75.    while (j < n) {
  76.       while (i > -1 && x[i] != y[j])
  77.          i = mpNext[i];
  78.       i++;
  79.       j++;
  80.       if (i >= m) {
  81.          cout<<(j - i)<<"\n";
  82.          i = mpNext[i];
  83.       }
  84.    }
  85. }
  86.  
  87.  
  88.    
  89.  
  90.     
  91.  
  92.  
  93.  
  94. int main()
  95. {   char wait;
  96.     ForzaBruta("pippo",5,"ho incontrato pippo rossi e pippo bianchi",38);
  97.     ForzaBruta2("pippo",5,"ho incontrato pippo rossi e pippo bianchi",38);
  98.     KarpRabin("pippo",5,"ho incontrato pippo rossi e pippo bianchi",38);
  99.     MorrisPratt("pippo",5,"ho incontrato pippo rossi e pippo bianchi",38);
  100.     cin>>wait;
  101. }
  102.