## 3 Flexible Head-Body Matching Algorithm
```
Input:\(AC\_DFA\) (a DFA constructed with AC algorithm) \(HSIZE\) (maximum level of head size) Output:\(HEAD\) (set of head states) \(HEAD\leftarrow\varnothing\); for\(h\gets 0\)to\(AC\_DFA\_MAX\_DEPTH\)do ifHEAD.size(\(0\)) + \(AC\_DFA\_depth[h]\_size()\leq HSIZE\)then HEAD =HEAD \(\cup\)\(AC\_DFA\_depth[h]\); else \(T\leftarrow\varnothing\); foreach state \(p\) in \(AC\_DFA\_level[h-1]\)do // \(p\_childStates()\) returns the set of child states of state \(p\). \(T\gets T\cup(p,p\_childStates()\_size())\);  end for Sort \(T\) by the second coordinate in descending order; foreach (\(s\),\(n\)) in \(T\)do ifHEAD.size() + \(n\leq HSIZE\)then foreach state \(t\) in \(s\_childStates()\)do \(HEAD\gets HEAD\cup t\);  end if ifHEAD.size() = HSIZE then  returnHEAD;  end if  end if  end if break;  end if returnHEAD;
```  
**Algorithm 1** Partitioning Algorithm  
```
Input:\(AC\_DFA\) (a DFA constructed with AC algorithm) \(HSIZE\) (maximum level of head size) Output:\(HEAD\) (set of head states) \(HEAD\leftarrow\varnothing\); for\(h\gets 0\)to\(AC\_DFA\_MAX\_DEPTH\)do ifHEAD.size(\(0\)) + \(AC\_DFA\_depth[h]\_size()\leq HSIZE\)then HEAD =HEAD \(\cup\)\(AC\_DFA\_depth[h]\); else \(T\leftarrow\varnothing\); foreach state \(p\) in \(AC\_DFA\_level[h-1]\)do // \(p\_childStates()\) returns the set of child states of state \(p\). \(T\gets T\cup(p,p\_childStates()\_size())\);  end for Sort \(T\) by the second coordinate in descending order; foreach (\(s\),\(n\)) in \(T\)do ifHEAD.size() + \(n\leq HSIZE\)then foreach state \(t\) in \(s\_childStates()\)do \(HEAD\gets HEAD\cup t\);  end if ifHEAD.size() = HSIZE then  returnHEAD;  end if  end if  end if break;  end if returnHEAD;
```  
**Algorithm 2** Partitioning Algorithm  
Given pattern set \(S\) = {account, advance, in, inner, insert, invert, stand, stood}, the AC-DFA can be constructed as shown in Figure 2. Numbered circles represent states, with state 1 designated as the start state. A double circle represents a matching state. If a matching state is achieved, it indicates that at least one pattern has been found. For the sake of clarity, Figure 2 omits all backward transitions. Figure 1: An illustrative example of AC-DFA. Assume a maximum head size of 12 states. According to the FHBM algorithm shown in Algorithms 1, the start state (state 1) is the first to be added to the head part, after which the three states in depth 1 are also added, since \(HEAD.size()+AC\_DATA.depth[1]=1+3<=HSIZE\). Similarly, states at depth 2 are added to the head part, increasing the number of states in the head part to 8. Since the number of states at depth 3 is also 8, the addition of all states to that depth will exceed the maximum head size, thus triggering the execution of the else part in Lines 6-21. Recall that the value of variable \(h\) is 3. After executing the foreach loop in Lines 7-9, \(T=\{(5,1),(6,1),(7,4),(8,2)\}\). Set \(T\) is sorted by the second coordinate in descending order, resulting in \(T=\{(7,4),(8,2),(5,1),(6,1)\}\). The foreach loop in Lines 11-20 initially selects (7, 4) and checks to see if all child states of state 7 can be added to the head part. Since \(HEAD.Size()+n=8+4<=HSIZE\), all child states of state 7 are added to the head part. Since the head part is filled to maximum, the partitioning algorithm is terminated by returning the head part. Figure 3 shows the AC-DFA head and body parts after partitioning. Figure 3: Head and body parts for the example AC-DFA. Figure 2: AC-DFA for the \(S\) pattern set.