## 2 Boyer-Moore Algorithm and Its Variants
### Quick Search Algorithm  
The quick search(QS) algorithm introduced by [PERSON] (1977) is a simplification of the Boyer-Moore algorithm without the good suffix rule. QS preprocesses pattern \(P\) using a modified \(bad\_shift\) array (called \(qbad\_shift\)) of length \(|\Sigma|\) in a time complexity of \(\Theta(m+|\Sigma|)\). The modified quick search bad shift array is defined as follows:  
\[qbad\_shift(\sigma)=\min(m-k:\{0\leq k\leq m-1|p[m-k-1]=\sigma,\sigma\in\Sigma \}\cup\{m+1\}) \tag{2}\]  
The preprocessing steps of the quick search algorithm are shown in Algorithm 1. In Algorithm 1, array \(qsBc\) is the quick search bad character shift array, which is initialized to value \(m\) from Line 1 to Line 3. Lines 4-6 implement Equation (2). For example, in the case of pattern \(P\) = \"GCAGTCAG\" with \(m=8\) and \(\Sigma=\{A,\ C,\ G,\ T\}\). Each element in \(bad\_shift\) array \(qsBc[A,\ C,\ G,\ T]\) is initialized to eight. After executing the \(for\)loop from Line 4 to Line 6, we have the \(bad\_shift\) array \(qsBc[A,\ C,\ G,\ T]=[2,3,1,4]\). ```
1 for\(i\leftarrow\) 0 to \(|\Sigma|\)-1
2 qsBc[\(i\)] \(\gets m\)
3 endfor
4 for\(i\leftarrow\) 0 to \(m-1\)
5 qsBc[P[\(i\)]] \(\gets m-i\)
6 endfor
7 returnqsBC[]
```  
**Algorithm 1** The preprocessing of the quick search algorithm. In Algorithm 1, Lines 1-3 run in \(|\Sigma|\) steps; Lines 4-6 run in \(m\) steps. Thus, the total preprocessing time is \(\Theta(m+|\Sigma|)\). Algorithm 2 shows the quick search algorithm. First, it calls the preprocessing procedure, \(preQS\), to compute the bad shift array. Lines 3-9 use a \(while\)loop to compare the text, \(T\), and the pattern, \(P\). Line 4 compares \(P[0,...,m-1]\) and \(T[j,...,j+m-1]\), where \(0\leq j\leq n-m\). When a mismatch occurs, the QS algorithm shifts to a new position as determined by the bad character in \(T\), that is, using the corresponding shift value for the symbol, \(T[j+m]\). ```
1 shift \(\leftarrow\) preQS(P,m)
2\(j\leftarrow\) 0
3 while (\(j\leq n-m\))
4 Compare \(P[0,...,m-1]\) and \(T[j,...,j+m-1]\)
5 if all matched then do
6 output \(j\)
7 endif
8\(j\gets j+shift[T[j+m]]\)
9 endwhile
```  
**Algorithm 2** The quick search algorithm. The searching phase of the QS has a worst case time complexity of \(O(mn)\). In the case of each time, a shift distance is maintained as on,e and the bad character is found in the last comparison of \(P[0]\) to the corresponding text (QS starts the comparison from right to left). For example, if \(T=A^{n}\) and \(P=BA^{m-1}\), in this case, the shift distance \(qsBc[A]=1\). That is, when each bad character occurs, the shift distance is one. Additionally, the bad character is found at the last comparison of \(P[0]\) to the corresponding text place, because the QS comparison is from right to left. However, this extreme worst case is rare. Just like the BM, the QS has a very good practical performance in general [10]. The QS algorithm was motivated by another simplification of the BM algorithm proposed earlier by [PERSON] in 1980 [14]. It has a better performance than the BM in the case of smaller alphabet sizes. The average number of comparisons for one character is between \(\frac{1}{|\Sigma|}\) and \(\frac{2}{|\Sigma|+1}\)[14]. It has the same preprocessing time of \(\Theta(m+|\Sigma|)\) and the worst-case searching time of \(O(mn)\), as with the QS algorithm. Another QS variant is the FJS algorithm, introduced by [PERSON], [PERSON] and [PERSON] [13] in 2007. FJS is a hybrid exact string matching algorithm that uses both the QS (_i.e._, Boyer-Moore) and Knuth-Moris-Pratt(KMP) algorithms. It has a \(\Theta(n+m)\) preprocessing time, similar to the QS. FJS uses the KMP algorithm to ensure that, in the worst-case, its searching phase is \(O(n)\), which is better in theory than the \(O(mn)\) of BM, QS and other QS variants. As shown in [13], when the pattern length is small (less than 10 characters), FJS's performance is slightly better than the other algorithms.