    Next: Tuned Boyer-Moore algorithm Up: ESMAJ Prev: Horspool algorithm

# Quick Search algorithm

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

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

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.

The C code
```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 */
}
}

```
The example

Preprocessing phase qsBc table used by Quick Search algorithm

Searching phase

References
• 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.    Next: Tuned Boyer-Moore algorithm Up: ESMAJ Prev: Horspool algorithm

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