karp.c

   1 #include "code.h"
   2
   3 int calculate_actual_match(char **text, char **pattern, int m, int n, 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 unsigned int karp(char **text, char **pattern, int m, int n)
  21 {
  22         unsigned int i, j;
  23
  24         double Bm = 1;
  25
  26         #define B 128
  27
  28         unsigned int row, matches = 0;
  29
  30         double pattern_hash = 0, text_hash = 0;
  31
  32         double vertical_pattern, vertical_text, vertical_previous_text;
  33
  34         /*Compute the hash for the pattern*/
  35         for( i = 0; i < m; i++ ) {
  36
  37                 Bm *= B;
  38
  39                 vertical_pattern = 0;
  40
  41                 /*Sum m characters in the same row*/
  42                 for( j = 0; j < m; j++ )
  43                         vertical_pattern += pattern[j][i];
  44
  45                 pattern_hash = pattern_hash * B + vertical_pattern;
  46         }
  47
  48         /*Compute the hash for the text*/
  49         for( row = 0; row < n - m + 1; row++ ) {
  50
  51                 text_hash = 0;
  52
  53                 /*Compute the hash for the first m elements of each row of the text*/
  54                 for( i = 0; i < m; i++ ) {
  55
  56                         vertical_text = 0;
  57
  58                         /*Sum m characters in the same row*/
  59                         for( j = 0 + row; j < m + row; j++ )
  60                                 vertical_text = vertical_text + text[j][i];
  61
  62                         text_hash = text_hash * B + vertical_text;
  63                 }
  64
  65                 /*Compute the hash for the rest n-m elements of each row of the text*/
  66                 for( i = m; i < n; i++ ) {
  67
  68                         /*Check if the hashes actually match*/
  69                         if( pattern_hash == text_hash && calculate_actual_match( text, pattern, m, n, i - m, row ))
  70                                 matches++;
  71
  72                         /* Update text's hash*/
  73                         vertical_text = 0;
  74                         vertical_previous_text = 0;
  75
  76                         /*Sum m characters from i-m (vpt) and from i (vt) */
  77                         for( j = 0 + row; j < m + row; j++ ) {
  78                                 vertical_previous_text = vertical_previous_text + text[j][i-m];
  79                                 vertical_text = vertical_text + text[j][i];
  80                         }
  81
  82                         text_hash = ( text_hash * B ) - ( vertical_previous_text * Bm ) + vertical_text;
  83                 }
  84         }
  85         return matches;
  86 }
  87