Berry-Ravindran algorithm

Berry and Ravindran designed an algorithm which performs the shifts by considering the bad-character shift (see chapter Boyer-Moore algorithm) for the two consecutive text characters immediately to the right of the window.

The preprocessing phase of the algorithm consists in computing for each pair of characters (a, b) with a, b in the rightmost occurrence of ab in axb. For a, b in

The preprocessing phase is in O(m+²) space and time complexity.

After an attempt where the window is positioned on the text factor y[j .. j+m-1] a shift of length brBc[y[j+m],y[j+m+1]] is performed. The text character y[n] is equal to the null character and y[n+1] is set to this null character in order to be able to compute the last shifts of the algorithm.

The searching phase of the Berry-Ravindran algorithm has a O(mn) time complexity.

void preBrBc(char *x, int m, int brBc[ASIZE][ASIZE]) {
   int a, b, i;

   for (a = 0; a < ASIZE; ++a)
      for (b = 0; b < ASIZE; ++b)
         brBc[a][b] = m + 2;
   for (a = 0; a < ASIZE; ++a)
      brBc[a][x[0]] = m + 1;
   for (i = 0; i < m - 1; ++i)
      brBc[x[i]][x[i + 1]] = m - i;
   for (a = 0; a < ASIZE; ++a)
      brBc[x[m - 1]][a] = 1;
}


void BR(char *x, int m, char *y, int n) {
   int j, brBc[ASIZE][ASIZE];

   /* Preprocessing */
   preBrBc(x, m, brBc);

   /* Searching */
   y[n + 1] = '\0';
   j = 0;
   while (j <= n - m) {
      if (memcmp(x, y + j, m) == 0)
         OUTPUT(j);
      j += brBc[y[j + m]][y[j + m + 1]];
   }
}