Smith algorithm

Smith noticed that computing the shift with the text character just next the rightmost text character of the window gives sometimes shorter shift than using the rightmost text character of the window.
He advised then to take the maximum between the two values.

The preprocessing phase of the Smith algorithm consists in computing the bad-character shift function (see chapter Boyer-Moore algorithm) and the Quick Search bad-character shift function (see chapter Quick Search algorithm).

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

The searching phase of the Smith algorithm has a quadratic worst case time complexity.

void SMITH(char *x, int m, char *y, int n) {
   int j, bmBc[ASIZE], qsBc[ASIZE];

   /* Preprocessing */
   preBmBc(x, m, bmBc);
   preQsBc(x, m, qsBc);

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