多模式串匹配之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 .2 3、 当状态转移到 2,5,7,9 等红色状态点时,说明发生了模式匹配。 如主串为:ushers,则在状态 5、2、9 等状态时发生模式匹配,匹配的模 式串有 she、he、hers。 定义: 在预处理阶段,AC 自动机算法建立了三个函数,转向函数 goto,失效函数 failure 和输出函数 output,由此构造了一个树型有限自动机。 转向函数,指的是一种状态之间的转向关系。g(pre, x)=next:状态 pre 在输入一个字符 x 后转换为状态 next(上图中的实线部分)。如果在模式串中不存在这样的转换,则 next=failstate。 失效函数,指的也是状态和状态之间一种...