## 3 The FQS Algorithm
### Search Phase  
In the search phase, FQS starts to compare the position in the pattern, \(P\), which has the maximal expected shift value, rather than the rightest-most position in \(P\), as in the QS (and the other BM variants). Algorithm 4 shows the detailed steps.  
```
FQS(\(P,m,T,n,|\Sigma|\))
1 pos\(\leftarrow\)GetPos (P,m,\(|\Sigma|\))
2 next\(\leftarrow\)preQS(P,pos)
3 shift\(\leftarrow\)preQS(P,m)
4\(j\leftarrow\)0
5 while(\(j\leq n-m\))
6 while(P[pos]\(\
eq\)T[j+pos])
7\(j\gets j+next[T[j+pos]]\)
8 if\(j>n-m\)thendo
9 return
10 endif
11 endwhile
12 Compare \(P[0,...,m-1]\) and \(T[j,...,j+m-1]\)
13 if all matched then do
14 output \(j\)
15 endif
16\(j\gets j+shift[T[j+m]]\)
17 endwhile
```  
**Algorithm 4** FQS pattern matching algorithm.  
In Algorithm 4, the first three lines are the preprocessing steps. Line 1 calls Algorithm 3 to get the location, \(pos\), with the maximal expected shift. Lines 2 and 3 calculate two shift tables (called \(next\) and \(shift\)) for the prefix \(P[0,...,pos-1]\) and the entire pattern, \(P\), respectively, using the same procedure as the classic QS preprocessing algorithm. Compared to the QS algorithm as shown in Algorithm 2, in the preprocessing phase, FQS adds two more lines: Lines 1 and 2. The total time complexity of the three steps is still \(O(m+|\Sigma|)\).  
FQS determines the maximal expected shift position. This maximal expected shift position has the statistical maximum shift distance. Once a mismatch is found, the algorithm jumps to a new position, which has the expected maximal shift distance. This mechanism significantly speeds up the FQS algorithm (see the section on the results).  
After the preprocessing step, the searching strategy of FQS is as follows:  
* Step 1: Check the symbols at maximal expected shift position \(pos\), that is, compare symbols \(P[pos]\) and \(T[j+pos]\);
* Step 2: If there is a mismatch, shift pattern \(P\) based on the distance determined by \(next[T[j+pos]]\). Go to Step 1 to continue checking position \(pos\);
* Step 3: If otherwise, compare \(P[0,...,m-1]\) to \(T[j,...,j+m-1]\), the same way as in the QS algorithm. If all matched, a matching pattern is found at position \(j\) in \(T\);
* Step 4: Whether all matched or not, shift the pattern to the right based on the value of \(shift[T[j+m]]\) using the classic quick search algorithm;
* Step 5: Repeat the above Steps 1-4 in a loop until text \(T\) is exhausted (\(j>n-m\)).  
In Algorithm 4, Lines 5-17 capture the searching phase. Compared with the QS algorithm, FQS adds Lines 6-11 in the search phase. In this phase, initially, text \(T\) is aligned with pattern \(P\), at positions \(T[j]\) and \(P[0]\), respectively, where \(0\leq j\leq n-m\). FQS first starts to compare the position of the maximal expected shift, \(pos\) in \(P\), to the corresponding position, \(j+pos\) in \(T\). If a mismatch occurs, the pattern is shifted to a position that is determined by the value, \(next[T[j+pos]]\). These steps are performed in Lines 6-11. Otherwise, the FQS algorithm does the same thing as the QS algorithm by starting to compare pattern \(P[0,...,m-1]\) and \(T[j,...,j+m-1]\) from right to left.