Name
• String
• Substring
• Search
Edit

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 xm+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.

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.

Example:

Preprocessing phase qsBc table used by Quick Search algorithm

Searching phase:

 G C A T C G C A G A G A G T A T A C A G T A C G 1 2 3 4 G C A G A G A G

Shift by: 1 (qsBc[G])

 G C A T C G C A G A G A G T A T A C A G T A C G 1 G C A G A G A G

Shift by: 2 (qsBc[A])

 G C A T C G C A G A G A G T A T A C A G T A C G 1 G C A G A G A G

Shift by: 2 (qsBc[A])

 G C A T C G C A G A G A G T A T A C A G T A C G 1 2 3 4 5 6 7 8 G C A G A G A G

Shift by: 9 (qsBc[T])

 G C A T C G C A G A G A G T A T A C A G T A C G 1 G C A G A G A G

Shift by: 7 (qsBc[C])

The Quick Search algorithm performs 15 character comparisons on the example.

C