多模式串匹配之AC 自动机算法（Aho-Coras ick 算法）简介与C 语言程序实现源码参考 任侠 发布于 2011-03-22 22:27:53 一、概述 AC 自动机算法全称 Aho-Coras ick 算法，是一种字符串多模式匹配算法
该算法在 1975 年产生于贝尔实验室，是著名的多模匹配算法之一
AC 算法用于在一段文本中查找多个模式字符串，即给你很多字符串，再给你一段文本，让你在文本中找这些串是否出现过，出现过多少次，分别在哪里出现
该算法应用有限自动机巧妙地将字符比较转化为了状态转移
此算法有两个特点，一个是扫描文本时完全不需要回溯，另一个是时间复杂度为 O(n)，时间复杂度与关键字的数目和长度无关，但所需时间和文本长度以及所有关键字的总长度成正比
AC 算法有三个主要步骤，一个是字典树 tire 的构造，一个是搜索路径的确定（即构造失败指针），还有就是模式匹配过程
学习 AC 自动机算法之前，最好先熟悉 KMP 算法，因为 KMP 算法与字典树 tire 的构造很是类似
KMP 算法是一种经典的单字符串匹配算法
二、AC 算法思想 AC 算法思想：用多模式串建立一个确定性的树形有限状态机，以主串作为该有限状态机的输入，使状态机进行状态的转换，当到达某些特定的状态时，说明发生模式匹配
下图是多模式he/ she/ his /hers 构成的一个确定性有限状态机，做几点说明： 图 2
1 1、 该状态机优先按照实线标注的状态转换路径进行转换，当所有实线标注的状态转换路径条件不能满足时，按照虚线的状态转换路径进行状态转换
如：状态 0 时，当输入 h，则转换到状态 1；输入 s，则转换到状态 3；否则转换到状态0
2、 匹配过程如下：从状态 0 开始进行状态转换，主串作为输入
如主串为：ushers，状态转换的过程是这样的： 图 2
