Raita algorithmESMAJBerry-Ravindran algorithmContents
Next: Raita algorithm Up: ESMAJ Prev: Berry-Ravindran algorithm

Smith algorithm


Main features
Description

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+sigma) time and O(sigma) space complexity.

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

The C code

The function preBmBc is given chapter Boyer-Moore algorithm and the function preQsBc is given chapter Quick Search algorithm.

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]]);
   }
}

The example

Preprocessing phase

Smith algorithm tables
bmBc and qsBc tables used by Smith algorithm.

Searching phase


References


Raita algorithmESMAJBerry-Ravindran algorithmContents
Next: Raita algorithm Up: ESMAJ Prev: Berry-Ravindran algorithm

e-mails: {Christian.Charras, Thierry.Lecroq }@laposte.net
Tue Jan 14 15:03:31 MET 1997