Boyer-Moore algorithmESMAJApostolico-Crochemore algorithmContents
Next: Boyer-Moore Up: ESMAJ Prev: Apostolico-Crochemore

Not So Naive algorithm


Main features
Description

During the searching phase of the Not So Naive algorithm the character comparisons are made with the pattern positions in the following order 1, 2, ... , m-2, m-1, 0.

For each attempt where the window is positioned on the text factor y[j .. j+m-1]: if x[0]=x[1] and x[1] neq y[j+1] of if x[0] neq x[1] and x[1]=y[j+1] the pattern is shifted by 2 positions at the end of the attempt and by 1 otherwise.

Thus the preprocessing phase can be done in constant time and space. The searching phase of the Not So Naive algorithm has a quadratic worst case but it is slightly (by coefficient) sub-linear in the average case.

The C code
void NSN(char *x, int m, char *y, int n) {
   int j, k, ell;
  
   /* Preprocessing */
   if (x[0] == x[1]) {
      k = 2;
      ell = 1;
   }
   else {
      k = 1;
      ell = 2;
   }
  
   /* Searching */
   j = 0;
   while (j <= n - m)
      if (x[1] != y[j + 1])
         j += k;
      else {
         if (memcmp(x + 2, y + j + 2, m - 2) == 0 &&
             x[0] == y[j])
            OUTPUT(j);
         j += ell;
      }
}

The example

Preprocessing phase

k=1 and ell=2

Searching phase


References


Boyer-Moore algorithmESMAJApostolico-Crochemore algorithmContents
Next: Boyer-Moore Up: ESMAJ Prev: Apostolico-Crochemore

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