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 SigmaqsBc[c]=min{i : 0  < i leq m and x[m-i]=c} if c occurs in xm+1 otherwise (thanks to Darko Brljak).

The preprocessing phase is in O(m+sigma) time and O(sigma) 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+sigma) time and O(sigma) space complexity;
  • searching phase in O(mn) time complexity;
  • very fast in practice for short patterns and large alphabets.

Example:

Preprocessing phase

Quick Search algorithm qsBc table
qsBc table used by Quick Search algorithm

Searching phase:

First attempt
GCATCGCAGAGAGTATACAGTACG
1234 
GCAGAGAG 

Shift by: 1 (qsBc[G])

Second attempt
GCATCGCAGAGAGTATACAGTACG
 1 
 GCAGAGAG 

Shift by: 2 (qsBc[A])

Third attempt
GCATCGCAGAGAGTATACAGTACG
 1 
 GCAGAGAG 

Shift by: 2 (qsBc[A])

Fourth attempt
GCATCGCAGAGAGTATACAGTACG
 12345678 
 GCAGAGAG 

Shift by: 9 (qsBc[T])

Fifth attempt
GCATCGCAGAGAGTATACAGTACG
 1 
 GCAGAGAG 

Shift by: 7 (qsBc[C])

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

C