karp.c

   1 #include "code.h"
   2
   3 int calculate_actual_match(int x, int y)
   4 {
   5         unsigned int i = 0, k, j, l, hit = 0;
   6
   7         for( l = y; l < m + y; l++, i++ ) {
   8
   9                 k = 0;
  10
  11                 for( j = x; j < m + x; j++, k++ )
  12                         if( pattern[i][k] == text[l][j] )
  13                                 hit++;
  14         }
  15         if ( hit == m*m )
  16                 return 1;
  17         return 0;
  18 }
  19
  20 void karp()
  21 {
  22         int steps = 0;
  23         unsigned int i, j, start = m;
  24
  25         double Bm = 1;
  26
  27         #define B 128
  28
  29         unsigned int row, matches = 0;
  30
  31         double pattern_hash = 0, text_hash = 0;
  32
  33         double vertical_pattern, vertical_text, vertical_previous_text;
  34
  35         /*Compute the hash for the pattern*/
  36         for( i = 0; i < m; i++ ) {
  37
  38                 Bm *= B;
  39
  40                 vertical_pattern = 0;
  41
  42                 /*Sum all characters in the same row*/
  43
  44                 for( j = 0; j < m; j++ )
  45                         vertical_pattern += pattern[j][i];
  46
  47                 pattern_hash = pattern_hash * B + vertical_pattern;
  48         }
  49
  50         /*Compute the hash for the first m elements of the first row of the text*/
  51
  52         for( i = 0; i < m; i++ ) {
  53
  54                 vertical_text = 0;
  55
  56                 /*Sum all characters in the same row*/
  57                 for( j = 0; j < m; j++ )
  58                         vertical_text = vertical_text + text[j][i];
  59
  60                 text_hash = text_hash * B + vertical_text;
  61         }
  62
  63         /*Compute the hash for the rest of the text*/
  64         for( row = 0; row < n - m + 1; row++ ) {
  65
  66                 /* On the first row start from the mth character */
  67                 if (row != 0)
  68                         start = 0;
  69
  70                 for( i = start; i < n; i++ ) {
  71
  72                         /*Check if the hashes actually match*/
  73
  74                         steps++;
  75
  76                         if( pattern_hash == text_hash && calculate_actual_match( i - m, row ))
  77                                 matches++;
  78
  79                         /* Update text's hash*/
  80                         vertical_text = 0;
  81                         vertical_previous_text = 0;
  82
  83                         for( j = 0 + row; j < m + row ; j++ ) {
  84                                 vertical_previous_text = vertical_previous_text + text[j][i-m];
  85                                 vertical_text = vertical_text + text[j][i];
  86                         }
  87
  88                         text_hash = ( text_hash * B ) - ( vertical_previous_text * Bm ) + vertical_text;
  89                 }
  90         }
  91         printf("Karp: %i\n",steps);
  92 }
  93