bird2.c

   1 #include "code.h"
   2
   3 int naive3( int textrow, int textcolumn, int patternrow, int patterncolumn )
   4 {
   5         unsigned int i, j, k;
   6
   7         for(i = textcolumn; i < patterncolumn; i++) {
   8
   9                 k = i;
  10
  11                 for(j = 0; j < m; j++) {
  12
  13                         if( pattern[patternrow][j] == text[textrow][k])
  14                                 k++;
  15
  16                         else
  17                                 break;
  18                 }
  19
  20                 if (j == m)
  21                         return k-m;
  22
  23                 else
  24                         j = 0;
  25
  26         }
  27         /* No match found on this row */
  28         return -1;
  29 }
  30
  31 void bird2()
  32 {
  33         int steps = 0;
  34
  35         /* x and y can be -1 */
  36         int x, y;
  37
  38         unsigned int i, row, matches = 0;
  39
  40         /* Iterate rows */
  41         for ( row = 0; row < n - m + 1; row++ ) {
  42
  43                 x = 0;
  44
  45                 /* Iterate through results on the same row */
  46                 while ( x != -1 ) {
  47
  48                         x = naive3( row, x, 0, n - m );
  49
  50                         steps++;
  51
  52                         /* If a row is found, check the m - 1 rows underneath it for matches */
  53                         if ( x != -1 ) {
  54
  55                                 for ( i = 1; i < m; i++) {
  56                                         /* Optimization: instead of checking against n chars on
  57                                          subsequent rows, just check against the next m chars after x */
  58                                         y = naive3( row + i, x, i, x + m );
  59
  60                                         steps++;
  61
  62                                         if ( y != x )
  63                                                 break;
  64
  65                                         /* If we reached to the final line above x without breaking, we have a match */
  66                                         else if ( i == m -1)
  67                                                 matches++;
  68                                 }
  69                                 /* After each attempt,increase the counter + 1 */
  70                                 x++;
  71                         }
  72                 }
  73         }
  74         printf("Bird2: %i\n",matches);
  75 }