- simplification of the Boyer-Moore algorithm;
- uses only the bad-character shift;
- easy to implement;
- preprocessing phase in
(**O***m*+) time and() space complexity;**O** - searching phase in
(**O***m**n*) time complexity; - very fast in practice for short patterns and large alphabets.

The Quick Search algorithm uses only the bad-character shift table (see chapter Boyer-Moore algorithm). After an attempt where the window is positioned on the text factor *y*[*j* .. *j*+*m*-1], the length of the shift is at least equal to one. So, the character *y*[*j*+*m*] is necessarily involved in the next attempt, and thus can be used for the bad-character shift of the current attempt.

The bad-character shift of the present algorithm is slightly modified to take into account the last character of *x* as follows: for *c* in , *qsBc*[*c*]=*min*{i : 0 < *i* *m* and *x*[*m*-*i*]=*c*} if *c* occurs in *x*, *m*+1 otherwise (thanks to Darko Brljak).

The preprocessing phase is in * O*(

During the searching phase the comparisons between pattern and text characters during each attempt can be done in any order. The searching phase has a quadratic worst case time complexity but it has a good practical behaviour.

void preQsBc(char *x, int m, int qsBc[]) { int i; for (i = 0; i < ASIZE; ++i) qsBc[i] = m + 1; for (i = 0; i < m; ++i) qsBc[x[i]] = m - i; } void QS(char *x, int m, char *y, int n) { int j, qsBc[ASIZE]; /* Preprocessing */ preQsBc(x, m, qsBc); /* Searching */ j = 0; while (j <= n - m) { if (memcmp(x, y + j, m) == 0) OUTPUT(j); j += qsBc[y[j + m]]; /* shift */ } }

Preprocessing phase

*qsBc* table used by Quick Search algorithm

Searching phase

- CROCHEMORE, M., LECROQ, T., 1996, Pattern matching and text compression algorithms, in
*CRC Computer Science and Engineering Handbook*, A. Tucker ed., Chapter 8, pp 162-202, CRC Press Inc., Boca Raton, FL. - LECROQ, T., 1995, Experimental results on string matching algorithms,
*Software - Practice & Experience*25(7):727-765. - STEPHEN, G.A., 1994,
*String Searching Algorithms*, World Scientific. **SUNDAY D.M.**, 1990, A very fast substring search algorithm, Communications of the ACM . 33(8):132-142.

Tue Jan 14 15:03:31 MET 1997