## 3 Flexible Head-Body Matching Algorithm  
As shown in Algorithms 1, our proposed FHBM algorithm uses an AC-DFA plus a pre-defined maximum head size as the input, and then partitions the AC-DFA into a head and a body. After all head part states are returned, both head and body parts are processed using the HBM algorithm. More specifically, the head part remains the same structure as an AC-DFA, while the body part is converted to a compact NFA for parallel processing. The head part is initially set to empty (Line 1). An AC-DFA can be analyzed as having a tree structure (Figure 1). If there is a valid transition from state \(A\) to state \(B\), then state \(A\) is considered a parent of state \(B\) and state \(B\) a child of state \(A\). State depth is defined as the number of edges that separate it from a root state that has a depth of 0. All states are processed starting from the root state. For each depth \(h\), the first task is to determine whether all states at that depth can be included in the head part. If the sum of the number of states in the head part (_HEAD.size_(0)) and the number of states at that depth (_AC_DFA.depth_[_h_]_size_(0)) is less than or equal to the maximum head size (_HSIZE_), then all states at that depth can be included in the head part (Line 4). Otherwise, the depth contains too many states to be entirely included in the head part. Note that the HBM algorithm partitions the AC-DFA based on a pre-defined depth value. Accordingly, states at the same depth are entirely included in either the head part or body part. However, since the number of states at any specific depth can be very large, including all states at the same depth in either the head part or body part cannot achieve good throughput. Our proposed FHBM algorithm lacks this restriction, and can therefore select appropriate states for inclusion in the head part. In the example presented in Figure 1, assume that the number of states at depths lower than \(h\)-1 is less than _HSIZE_, and that the number of states at depth \(h\) is too large for inclusion in the head part. According to both the HBM and our proposed algorithms, states at depths lower than \(h\)-1 are partitioned in the head part. One straightforward method for fully utilizing _HSIZE_ is to include states at depth \(h\) one-by-one until there is no available room for additional states. However, according to the head and body part structures, all states with the same parent state must be 100% in the head part or 100% in the body part. As shown in Figure 1, state \(s\) has four child states. If only a partial number of child states are partitioned in the head part, the HBM algorithm cannot build the body part. Thus, the problem is to include as many states at depth \(h\) as possible in the head part according the _HSIZE_ constraint, and to guarantee that states with the same parent state are either entirely included or excluded from the head part. The optimal solution for this problem makes use of the greedy algorithm described below. First, a temporary set named \(T\) (in which each element is an ordered pair denoted by \((s,n)\)) is used to store the information of a state \(s\) at depth \(h\)-1 and a number of its child states (\(n\)) (Lines 7-9). Next, all elements in the set are sorted by the second coordinate (i.e., the number of child states) in descending order (Line 10). All elements in \(T\) are processed one-by-one starting with the largest number of states (Lines 11-20). Given that the currently processed element is \((s,n)\), if the number of states in the head part (after adding all child states of state \(s\)) does not exceed _HSIZE_, all child states of state \(s\) will be added to the head part (Lines 13-15). Otherwise, the next element in the temporary set will be processed. If all elements are processed, or if the size of _HEAD_ is equal to _HSIZE_, the outermost for-loop (Lines 2-23) will be terminated, after which the head set is returned (Line 24).