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         for(i = textcolumn; i < n - m; 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 unsigned int baeza2( char **text, char **pattern, int m, int n )
  32 {
  33         int x, y, i, j, row, matches = 0;
  34
  35         /* Iterate every m rows (first check lines 0 to m - 1) */
  36         for ( row = m - 1; row < n; row += m ) {
  37
  38                 /* Search the same row for occurences of the different lines of the pattern */
  39                 for ( i = 0; i < m; i++ ) {
  40
  41                         /* In each row start searching from the begining */
  42                         x = 0;
  43
  44                         while ( x != -1) {
  45
  46                                 /* Check text's row against each pattern's row */
  47                                 x = naive2( text, pattern, m, n, row, x, i);
  48
  49                                 /* If a row is not found procceed to the next row */
  50                                 if ( x != -1 ) {
  51
  52                                         /* If there is a match at i = 3, check vertically the text above for i = 0-2 and below for 4-m*/
  53
  54                                         /* Check lines above the current */
  55                                         for ( j = 0; j < i; j++ ) {
  56                                                 y = naive2( text, pattern, m, n, row - i + j, x, j);
  57
  58                                                 if ( y != x)
  59                                                         goto newline;
  60                                         }
  61
  62                                         /* Check lines below the current */
  63                                         for ( j = 1; j < m - i; j++ ) {
  64
  65                                                 /* Avoid crashing when x = n or n-1 */
  66                                                 if ( row + j >= n )
  67                                                         goto newline;
  68
  69                                                 y = naive2( text, pattern, m, n, row + j, x, i + j);
  70
  71                                                 if ( y != x )
  72                                                         goto newline;
  73                                         }
  74
  75                                         /* If we reached here we should have a match */
  76                                         matches++;
  77
  78                                 /* If a mismatch is found, don't bother searching for the other y lines */
  79                                 newline:
  80
  81                                         /* Now increase counter to continue searching on the same row */
  82                                         x++;
  83                                 }
  84                                 else break;
  85                         }
  86                 }
  87         }
  88         return matches;
  89 }