AC自动机基础介绍
AC自动机Aho-Corasick automation 用途 字符串的匹配 多串匹配问题 例如,给几个单词 acbs,asf,dsef, 再给出一个 长文章,acbsdfgeasf 问这篇文章中出现了多少个单词,或者出现了多少个单词。 实现的原理 形象的说:KMP trie树(字典树) 思考:在一棵树上trie树上面做Kmp,每个节点都有一个图像Kmp同样匹配失败时的指针(fail指针),按失败指针指向的节点继续匹配。 什么是trie树(字典树)? Trie树 有神马特点 有一个空根节点。 对于一般的trie数字是解决用英文字母组成文章的问题。所以每个节点都有26个子节点(指针)。 构造的过程 一开始就有一个root 过程 在树上插入一个单词she 过程 再加一个单词shr。 过程 再插入say和her等等,这样一个trie树就搞定了 如何与kmp联系在一起? 关键是在trie树上 加了一种fail指针。 Fail指针的用途:将当前字符不匹配时跳转到公共前后缀最长的字符继续匹配,就像 KMP算法一样, AC如果当前字符匹配失败,则使用自动机fail指针进行跳转。因此,如果跳转,跳转后串的前缀必须是跳转前模式串的后缀,跳转新位置的深度(匹配字符数量)必须小于跳转前的节点。所以我们可以使用它 bfs在 Trie上面进行 fail求解指针。 在字符串失配时确定转移节点。 先看看是什么样子 这只显示e的fail指针。 例如,匹配文章:sher 如何有效地构造前缀指针 1 2 3 6 4 5 7 8 A A A B B B B ROOT1号节点的前缀指针指向0号节点 接下来按照BFS每个节点的前缀指针顺序构建 定义虚拟节点0号节点,0号节点的所有连接字边都连接到方向ROOT1号节点 0 A、B 2号节点: 父亲是1号节点,连接字符是A,找出父亲的前缀指针0号节点,是否有儿子通过A连接。 有! 所以2号节点的前缀指针指向1号节点 3号节点: 父亲是1号节点,连接字符是B,找出父亲的前缀指针0号节点,是否有儿子通过B连接。 有!因此,3号节点的前缀指针指向1号节点 4号节点: 父亲是2号节点,连接字符是B,找出父亲的前缀指针1号节点,是否有儿子通过B连接。 有!因此,4号节点的前缀指针指向3号节点 5号节点: 父亲是3号节点,连接字符是A,找出父亲的前缀指针1号节点,是否有儿子通过A连接。 有!因此,5号节点的前缀指针指向2号节点 8号节点: 父亲是7号节点,连接字符是B,找出父亲的前缀指针5号节点,是否有儿子通过B连接。 不,继续寻找5号节点的前缀指针2号节点是否有儿子通过B连接。 有!因此,8号节点的前缀指针指向4号节点 7号节点: 父亲是4号节点,连接字符是A,找出父亲的前缀指针3号节点,是否有儿子通过A连接。 有!因此,7号节点的前缀指针指向5号节点 6号节点: 父亲是3号节点,连接字符是B,找出父亲的前缀指针1号节点,是否有儿子通过B连接。 有!因此,6号节点的前缀指针指向3号节点 到目前为止,我们已经设计了这棵树的前缀指针!! 插入n个模式串的单词前缀树结构前缀指针的时间复杂如下:O(∑len(i)) AC自动算法分为三个步骤: 1.构造一棵Trie树 2.构造fail指针 3.模式匹配过程 构造fail指针原理: 根据父亲节点fail构建子节点的指针fail指针。 hdu2222 5 //单词数 she //单词 he say shr her Yasherhs//文章 问单词数的和 代码实现 struct node { int next[26]; int fail; int count; void init() { memset(next, -1, sizeof(next)); fail = 0; count = 0; } }s[500005];