baeza2.c

   1 #include "code.h"
   2
   3 int naive2( char **text, char **pattern, int m, int n, int textrow, int textcolumn, int patternrow )
   4 {
   5         unsigned int i, j, k;
   6
   7         /* Slide the text's window */
   8         for ( i = textcolumn; i < n - m + 1; i++ ) {
   9
  10                 k = i;
  11
  12                 /* Start searching against the first pattern character */
  13                 for( j = 0; j < m; j++ ) {
  14
  15                         if( pattern[patternrow][j] == text[textrow][k] )
  16                                 k++;
  17
  18                         else
  19                                 break;
  20                 }
  21                 /* If j finished without breaking return success */
  22                 if ( j == m )
  23                         return k-m;
  24                 else
  25                         j = 0;
  26         }
  27         /* No match found on this row */
  28         return -1;
  29 }
  30
  31 int naive2b( char **text, char **pattern, int m, int n, int textrow, int textcolumn, int patternrow )
  32 {
  33         unsigned int j;
  34
  35         /* Search only m characters after the current text's column without sliding the window */
  36         for ( j = 0; j < m; j++ ) {
  37
  38                 if( pattern[patternrow][j] == text[textrow][textcolumn] )
  39                         textcolumn++;
  40
  41                 else
  42                         return -1;
  43         }
  44         /* If reached through here, report success */
  45         return 0;
  46 }
  47
  48 unsigned int baeza2( char **text, char **pattern, int m, int n )
  49 {
  50         int x, i, j, row, matches = 0;
  51
  52         /* Iterate every m rows of the text (first check lines 0 to m - 1) */
  53         for ( row = m - 1; row < n; row += m ) {
  54
  55                 /* Search each row against all m lines of the pattern */
  56                 for ( i = 0; i < m; i++ ) {
  57
  58                         /* In each row start searching from the begining */
  59                         x = 0;
  60
  61                         while ( x != -1) {
  62
  63                                 /* Check text's row against pattern's row */
  64                                 x = naive2( text, pattern, m, n, row, x, i);
  65
  66                                 /* If a row is not found procceed to the next pattern's row */
  67                                 if ( x != -1 ) {
  68
  69                                         /* If there is a match at i = 3, check vertically the text above for i = 0-2 and below for 4-m*/
  70
  71                                         /* Check lines above the current */
  72                                         for ( j = 0; j < i; j++ )
  73                                                 if( naive2b( text, pattern, m, n, row - i + j, x, j ) == -1)
  74                                                         goto newline;
  75
  76                                         /* Check lines below the current */
  77                                         for ( j = 1; j < m - i; j++ ) {
  78
  79                                                 /* Avoid crashing when x = n or n-1 */
  80                                                 if ( row + j >= n )
  81                                                         goto newline;
  82
  83                                                 if ( naive2b( text, pattern, m, n, row + j, x, i + j ) == -1)
  84                                                         goto newline;
  85                                         }
  86
  87                                         /* If we reached here we should have a match */
  88                                         matches++;
  89
  90                                 /* If a mismatch is found, don't bother searching for the other y lines */
  91                                 newline:
  92
  93                                         /* Now increase counter to continue searching on the same row */
  94                                         x++;
  95                                 }
  96                                 else break;
  97                         }
  98                 }
  99         }
 100         return matches;
 101 }