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, start = m;
  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 all characters in the same row*/
  42
  43                 for( j = 0; j < m; j++ )
  44                         vertical_pattern += pattern[j][i];
  45
  46                 pattern_hash = pattern_hash * B + vertical_pattern;
  47         }
  48
  49         /*Compute the hash for the first m elements of the first row of the text*/
  50
  51         for( i = 0; i < m; i++ ) {
  52
  53                 vertical_text = 0;
  54
  55                 /*Sum all characters in the same row*/
  56                 for( j = 0; j < m; j++ )
  57                         vertical_text = vertical_text + text[j][i];
  58
  59                 text_hash = text_hash * B + vertical_text;
  60         }
  61
  62         /*Compute the hash for the rest of the text*/
  63         for( row = 0; row < n - m + 1; row++ ) {
  64
  65                 /* On the first row start from the mth character */
  66                 if (row != 0)
  67                         start = 0;
  68
  69                 for( i = start; i < n; i++ ) {
  70
  71                         /*Check if the hashes actually match*/
  72                         if( pattern_hash == text_hash && calculate_actual_match( text, pattern, m, n, i - m, row ))
  73                                 matches++;
  74
  75                         /* Update text's hash*/
  76                         vertical_text = 0;
  77                         vertical_previous_text = 0;
  78
  79                         for( j = 0 + row; j < m + row ; j++ ) {
  80                                 vertical_previous_text = vertical_previous_text + text[j][i-m];
  81                                 vertical_text = vertical_text + text[j][i];
  82                         }
  83
  84                         text_hash = ( text_hash * B ) - ( vertical_previous_text * Bm ) + vertical_text;
  85                 }
  86         }
  87         return matches;
  88 }
  89