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
  16         if ( hit == m*m )
  17                 return 1;
  18         return 0;
  19 }
  20
  21 unsigned int karp(char **text, char **pattern, int m, int n)
  22 {
  23         unsigned int i, j;
  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 m characters in the same row*/
  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 text*/
  50         for( row = 0; row < n - m + 1; row++ ) {
  51
  52                 text_hash = 0;
  53
  54                 /*Compute the hash for the first m elements of each row of the text*/
  55                 for( i = 0; i < m; i++ ) {
  56
  57                         vertical_text = 0;
  58
  59                         /*Sum m characters in the same row*/
  60                         for( j = 0 + row; j < m + row; j++ )
  61                                 vertical_text = vertical_text + text[j][i];
  62
  63                         text_hash = text_hash * B + vertical_text;
  64                 }
  65
  66                 /*Compute the hash for the rest n-m elements of each row of the text*/
  67                 for( i = m; i < n; i++ ) {
  68
  69                         /*Check if the hashes actually match*/
  70                         if( pattern_hash == text_hash && calculate_actual_match( text, pattern, m, n, i - m, row ))
  71                                 matches++;
  72
  73                         /* Update text's hash*/
  74                         vertical_text = 0;
  75                         vertical_previous_text = 0;
  76
  77                         /*Sum m characters from i-m (vpt) and from i (vt) */
  78                         for( j = 0 + row; j < m + row; j++ ) {
  79                                 vertical_previous_text = vertical_previous_text + text[j][i-m];
  80                                 vertical_text = vertical_text + text[j][i];
  81                         }
  82
  83                         text_hash = ( text_hash * B ) - ( vertical_previous_text * Bm ) + vertical_text;
  84                 }
  85         }
  86         return matches;
  87 }
  88