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-1-i]=c} if c occurs in x, m otherwise.
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.
Hiç yorum yok:
Yorum Gönder