bm.c

   1 #include "code.h"
   2
   3 void heur1( int m, unsigned int *CharJump )
   4 {
   5         unsigned int i;
   6
   7         for ( i = 0; i < m; i++ )
   8                 CharJump[i] = m - i -1;
   9 }
  10
  11 void heur2( double *pattern2, int m, int n, unsigned int *MatchJump, unsigned int *BackUp )
  12 {
  13         unsigned int i, ia, ib;
  14
  15         for ( i = 1; i < m; i++ )
  16                 MatchJump[i] = 2 * m - i;
  17
  18         i = n;
  19         ia = n + 1;
  20
  21         while ( i > 0 ) {
  22
  23                 BackUp[i] = ia;
  24
  25                 while ( ia <= m && pattern2[i - 1] != pattern2[i -1] ) {
  26
  27                         if ( MatchJump[ia] > m - i )
  28                                 MatchJump[ia] = m - i;
  29                         ia = BackUp[ia];
  30                 }
  31                 i--;
  32                 ia--;
  33         }
  34
  35         for ( i = 1; i < ia; i++) {
  36
  37                 if ( MatchJump[i] > m + ia - i )
  38                         MatchJump[i] = m + ia - i;
  39         }
  40
  41         ib = BackUp[ia];
  42
  43         while ( ia <= m ) {
  44                 while ( ia <= ib ) {
  45
  46                         if ( MatchJump[ia] > ib - ia + m )
  47                                 MatchJump[ia] = ib - ia + m;
  48                         ia++;
  49                 }
  50                 ib = BackUp[ib];
  51         }
  52 }
  53
  54 int jump( double *text2, double *pattern2, int m, int mark, unsigned int *CharJump )
  55 {
  56         unsigned int i;
  57
  58         for ( i = 0; i < m; i++ )
  59                 if( text2[mark] ==  pattern2[i] )
  60                         return CharJump[i];
  61         return m;
  62 }
  63
  64 unsigned int search_bm( double *text2, double *pattern2, int m, int n )
  65 {
  66         #ifndef max
  67         #define max(a,b) ((a) > (b) ? (a) : (b))
  68         #endif
  69
  70         unsigned int *CharJump = ( unsigned int* ) malloc( m * sizeof( unsigned int* ));
  71
  72         if( CharJump == NULL ) {
  73                 printf("Failed to allocate array!\n");
  74                 exit(1);
  75         }
  76
  77         unsigned int *BackUp = ( unsigned int* ) malloc( n * sizeof( unsigned int* ));
  78
  79         if( BackUp == NULL ) {
  80                 printf("Failed to allocate array!\n");
  81                 exit(1);
  82         }
  83
  84         unsigned int *MatchJump = ( unsigned int* ) malloc ( 2 * sizeof ( unsigned int* ) * ( m + 1 ) );
  85
  86         if( MatchJump == NULL ) {
  87                 printf("Failed to allocate array!\n");
  88                 exit(1);
  89         }
  90
  91         unsigned int matches = 0;
  92
  93         unsigned int ia, ib;
  94
  95         unsigned int pattern_marker, text_marker;
  96
  97         pattern_marker = m;
  98
  99         text_marker = m -1;
 100
 101         /* bm uses two heuristics */
 102         heur1( m, CharJump );
 103
 104         heur2( pattern2, m, n, MatchJump, BackUp );
 105
 106         const int limit = n * n - ( n * ( m - 1 ) );
 107
 108         while ( text_marker < limit )
 109         {
 110                 /* We have a partial match */
 111                 if ( text2[text_marker] == pattern2[pattern_marker -1] ) {
 112                         pattern_marker--;
 113                         text_marker--;
 114                 }
 115
 116                 else {
 117                         ia = jump( text2, pattern2, m, text_marker, CharJump );
 118                         ib = MatchJump[pattern_marker];
 119                         text_marker += max( ia, ib );
 120                         pattern_marker = m;
 121                 }
 122
 123                 /* We have a match */
 124                 if ( pattern_marker == 0 ) {
 125                         matches++;
 126                         text_marker += m + 1;
 127                         pattern_marker = m;
 128                 }
 129         }
 130
 131         free( CharJump );
 132         free( BackUp );
 133         free( MatchJump );
 134
 135         return matches;
 136 }
 137