bird2.c

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