Not So Naive algorithm

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]  y[j+1] of if x[0]  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.

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