关键词: 改进的AC（AAC）算法, 多模式, 自动机, 模式匹配

Abstract: The AAC algorithm has high and stable performance. It is the most widely used multi-patterns string matching algorithm. In AAC, to determine whether the automaton reaches the final state（means a matching found）, the output table should be visited per character read, which produces high cost. To reduce the cost of output table visited, this paper improves AAC by two methods. One method is copying final states, adding them after the original automaton and modifying the transitions whose target state is final to the additive state. The other method is modifying the transitions whose target state is final and making the transition store the negative value of target state. Thereby, two algorithms are presented named Advanced AC with Additive state（AACA）and Advanced AC with Negative state（AACN）. These two algorithms can determine whether the automaton reaches the final state only by the value of the target state of transition and the visit of output table reduces from per character read to per matching occurrence. The experiment result indicates that AACA and AACN are faster than AAC, especially in small scale string matching. In the mean research field of the team, the timing models of Cyber-Physical Systems（CPS）, the multiple timing patterns matching in the timing reachability graph of the CPS is the key problem. Since the timing pattern is rapidly changed, the real-time of matching is more important while the scale of matching is not big. AACA and AACN fit this area which can increase the accuracy and real-time of hybrid embedded system timing models.

Key words: Advanced AC(AAC) algorithm, multi-patterns, automata, pattern matching