## 2 Pattern-Matching Algorithms Review
### Wu-Manber Algorithm  
The tables used in pattern matching are created by performing basic calculations required for the scanning phase in the preprocessing phase of the WM algorithm. During matching, a window of length m contains the characters to be inspected, and the matching result indicates the next position to which the window should be shifted. The length of the matching window, m, is determined by the shortest pattern length, and the shift distance of the matching window is calculated using the predetermined length of character blocks (usually two or three). The value B represents the length of the character block, the value m is the length of the matching window, and the value X is the character block at any position in the matching window. \(T=t_{1},t_{2},\ldots,t_{n}\) denotes the packet payload, n is the length of the packet payload, and the \(P=\{p_{1},p_{2},\ldots,p_{n}\}\) is the pattern set. Character blocks of size B are obtained using the first m characters in each pattern. Then, the shift distance values are calculated for each character block and stored in a SHIFT table. Suppose the value X is at the ith index in a SHIFT table. Here, the value i is obtained from hash calculations performed using the character block \(X\). The shift distance is calculated using Equation (1). \[\mathrm{SHIFT[i]}=\left\{ \begin{matrix}\mathrm{m-B+1,X}\text{ does not match any pattern}\\ \min\{\mathrm{m-q[k]=P_{j}[q-B+k],1\leq k\leq B,P_{j}\in P\}\}\end{matrix} \right. \tag{1}\]  
The q-value in Equation (1) denotes the location where the rightmost of the X-position is. REFIX tables serve to distinguish patterns with suffixes carrying identical hash values from each other. The suffix is the character block created with the last B characters of the first m characters of each pattern. The prefix of the first m characters of the patterns is employed instead of the suffix in the hash calculations in the PREFIX_value table. The values obtained as a result of hash calculations performed using the prefix of each pattern are stored in the PREFIX_value table. While the identity value of each pattern is stored in the PREFIX_index table, the PREFIX_size table keeps the number of patterns with the same suffix hash value. The pattern detection process for the WM algorithm is as follows:  
1. The matching window is placed to cover the first m characters of the packet payload. In this case, the packet payload pointer t\({}_{\mathrm{P}}\) represents the suffix character block of the matching window. 2. If the pointer value showing the last element of the packet payload is less than or equal to the value of the t\({}_{\mathrm{P}}\) pointer, the hash value of the suffix character block of the matching window is calculated. Otherwise, the matching process ends in the current packet. 3. This hash value is used in the search operation in a SHIFT table. If the shift distance of the character block is 0, it is possible that the matching window can be the first m characters of a pattern, and, in this case, it is possible to go to Step 4 for the prefixhash calculations. Otherwise, the t\({}_{\text{p}}\) value is increased by the shift distance, and the process returns to Step 2. 4. The prefix hash values of patterns with the same suffix hash calculation are compared with the hash value of the prefix character block of T in the matching window. 5. The pattern and packet payload are compared byte by byte if a correct comparison is detected in Step 4. If any match is found, the match is saved. The t\({}_{\text{p}}\) value is increased by one, and the process returns to Step 2. Let the N value represent the length of the scanned text, P value the number of patterns, and m value the length of the pattern. In this case, M = mP is the length of all patterns. If N \(\geq\) M, calculations on any B-length substring of the pattern are performed once, and a SHIFT table is created in O(M) time. The scanning time of the algorithm depends on whether the shift distance value is greater or less than zero.