## 3 A Novel Multi-Pattern-Matching Algorithm
### Proposed Algorithm
A character signature must be specific to each character, start with 0, and increase with each different character. A state signature should begin with 1 for each character and rise one by one for that character. When a different character comes in, it should start with 1 again. The next step after generating group codes is generating state codes (Table 2). All states from the same root are combined. Then, the character and state signatures of the destination states are combined to create a state code for each state. These codes are then used to find the next state based on the given character. The final step is to create two main tables used for pattern matching. These tables are the character/cluster table (CC) (Table 3) and code table (CO) (Table 4). The index value in the CC table is the failure field. In calculating the offset value, the incrementing process is performed by character repetition. For example, since the H character is repeated twice, the S character's offset is 2. These two tables then serve for pattern matching. Given a state and a character, Equation (2) shows the formula to calculate the next state. \[S_{\rm index}=\rm Ch_{offset}+S_{\rm sig} \tag{2}\] \begin{table}
\begin{tabular}{c c c c c} \hline
**Cluster** & **Character** & **Group** & **Char Signature** & **State Signature** \\ \hline C1 & H & G1 & 00 & 01 \\ C1 & H & G5 & 00 & 10 \\ C1 & S & G2 & 01 & 01 \\ C1 & S & G7 & 01 & 10 \\ C1 & S & G9 & 01 & 11 \\ C1 & E & G3 & 10 & 01 \\ C1 & E & G8 & 10 & 10 \\ C1 & R & G6 & 11 & 01 \\ C2 & I & G4 & 0 & 1 \\ \hline \end{tabular}
\end{table} 
Table 1: Group coding. \begin{table}
\begin{tabular}{c c c} \hline
**State** & **Group** & **Code** \\ \hline S1 & G3, G4 & 100101 \\ S2 & G5 & 001000 \\ S3 & G6 & 110100 \\ S4 & G7 & 011000 \\ S5 & G8, G4 & 101001 \\ S6 & G9 & 011100 \\ S7 & G5 & 001000 \\ S8 & G6 & 110100 \\ S9 & G5 & 001000 \\ \hline \end{tabular}
\end{table} 
Table 2: State codes. In Equation (2), the S\({}_{\rm Index}\) value represents the index field in the CO table, the Ch\({}_{\rm offset}\) value represents the offset field in the CC table, and the S\({}_{\rm sig}\) value represents the state signature in the state code. For example, let us calculate the next state at State 7 while the input character is H. First, the signature of the H character is determined as 00 from the CC table. Then, the signature of State 7 is checked on the CO table. Since equality is achieved, the addition process starts. The calculation of \((00)+(10)=2\) reveals the index value in the CO table as 2. The index value of 2 corresponds to State 5 in the CO table, and, thus, a transition to State 5 occurs. The state code length depends on the number of transitions from the current state to other states. The number of transitions depends on the presence of common roots of the patterns that form the automaton. As seen in Figure 6, since the common root of the \"ABKKLMN\" pattern with the \"ABKXYZMNO\" and \"ABKXYZABCD\" patterns is \"AB\", there is a transition from State 1 to two separate states. Again, since the common root of the \"ABKXYZMNO\" and \"ABKXYZABCD\" patterns is \"ABKXYZ\", there is a transition from State 3 to two separate states. A state code of the state with two transitions occurs by combining the information of two transitions. The information about a transition consists of a cluster, character signature, and state signature. If a pattern shares a common root with one or more patterns, a single transition representing all patterns with a common root is produced from State 0. For a pattern that does not share any common root with any pattern, a transition from State 0 is created, which represents only that pattern. The increase in the pattern numbers causes a large number of transitions from State 0, and the length of the code generated to store these transitions increases depending on the pattern numbers. This produces a transition to each cluster within the state code created for State 0. Therefore, identifying the next state process for State 0 differs from the procedure for other cases.