Name

Edit

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.

**Main features:**

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.

- preprocessing phase in constant time and space;
- searching phase in O(nm) time complexity;
- slightly (by coefficient) sub-linear in the average case.

C