bm.c

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