ac自动机以及它上面的DFA
- 博客分类:
- 数据结构算法
AC自动机(Aho-Corasick)主要用于多模式串的匹配问题,是前缀匹配搜索的一种方法,和KMP算法的思想类似。
总所周至,KMP算法中的关键next指针利用了模式串本身的性质,在失配时给出了重新匹配的位置。AC自动机中的fail指针也是一样,fail指针的构造关键是找到即是当点匹配串的后缀,又是trie中一个模式串的前缀的最长的字符串。
DFA是确定性有穷自动机,用于正则表达式的匹配,AC自动机可以用来构造DFA,将trie树中的节点看成是DFA中的状态,字符的匹配看成DFA的转化关系,再做一定的处理即可完成
AC自动机本质上来说是一种基于trie树的kmp算法。下面是AC自动机和DFA实现的代码:
#include <queue> #include <cstdio> #include <cstring> #include <cassert> #include <algorithm> #include <functional> using namespace std; struct AhoCorasick { static const int UNDEF = 0;//非终结标识符 static const int MAXN = 2048; static const int CHARSET = 2; int end;//节点尾 int tag[MAXN];//是否为终结节点1.是0.不是 int fail[MAXN];//失败指针 int trie[MAXN][CHARSET];//trie树 void init() { tag[0] = UNDEF; fill(trie[0], trie[0] + CHARSET, -1); end = 1; } //插入 void add(int m, const int* s, int t) { int p = 0; for (int i = 0; i < m; ++i) { if (trie[p][*s] == -1) { tag[end] = UNDEF; fill(trie[end], trie[end] + CHARSET, -1); trie[p][*s] = end++; } p = trie[p][*s]; ++s; } tag[p] = t; } //构造失败指针以及trie上的DFA void build() { queue<int> bfs; fail[0] = 0; for (int i = 0; i < CHARSET; ++i) { if (trie[0][i] != -1) { fail[trie[0][i]] = 0; bfs.push(trie[0][i]); } else { trie[0][i] = 0; } } while (!bfs.empty()) { int p = bfs.front(); tag[p] |= tag[fail[p]]; // bfs.pop(); for (int i = 0; i < CHARSET; ++i) { if (trie[p][i] != -1) { fail[trie[p][i]] = trie[fail[p]][i]; bfs.push(trie[p][i]); } else { trie[p][i] = trie[fail[p]][i]; } } } } } ac; const int MAXN = 218; const long long MOD = 1000000009LL; int next[AhoCorasick::MAXN][10]; long long dp[MAXN][AhoCorasick::MAXN]; char str[MAXN]; int num[MAXN]; int _next(int p, int x) { for (int i = 3; i >= 0; --i) { p = ac.trie[p][(x & (1 << i)) ? 1 : 0]; if (ac.tag[p] != AhoCorasick::UNDEF) { return -1; } } return p; } long long gao(int m, const int* s, int p) { if (p == -1) { return 0LL; } else if (m == 0) { return 1LL; } else { long long ret = 0LL; for (int i = 0; i < *s; ++i) { int q = next[p][i]; if (q != -1) { ret += dp[m - 1][q]; } } ret += gao(m - 1, s + 1, next[p][*s]); return ret % MOD; } } long long gao(int m, const int* s) { long long ret = 1LL; if (m > 0) { ret += gao(m - 1, s + 1, next[0][*s]); for (int i = 0; i < m; ++i) { for (int j = 1; j < (i == m - 1 ? *s : 10); ++j) { int p = next[0][j]; if (p != -1) { ret += dp[i][p]; } } } ret %= MOD; } return ret; } int main() { int re, n, m; long long ans; freopen("e:\\zoj\\zoj_3494.txt","r",stdin); scanf("%d", &re); for (int ri = 1; ri <= re; ++ri) { scanf("%d", &n); ac.init(); for (int i = 0; i < n; ++i) { scanf("%s", str); m = strlen(str); transform(str, str + m, num, bind2nd(minus<char>(), '0')); ac.add(m, num, 1); } ac.build(); for (int i = 0; i < ac.end; ++i) { for (int j = 0; j < 10; ++j) { next[i][j] = ac.tag[i] == AhoCorasick::UNDEF ? _next(i, j) : -1; } } for (int j = 0; j < ac.end; ++j) { dp[0][j] = ac.tag[j] != AhoCorasick::UNDEF ? 0 : 1; } for (int i = 1; i < MAXN; ++i) { for (int j = 0; j < ac.end; ++j) { dp[i][j] = 0; if (ac.tag[j] == AhoCorasick::UNDEF) { for (int k = 0; k < 10; ++k) { int jj = next[j][k]; if (jj != -1) { dp[i][j] += dp[i - 1][jj]; } } dp[i][j] %= MOD; } } } scanf("%s", str); m = strlen(str); transform(str, str + m, num, bind2nd(minus<char>(), '0')); for (int i = m - 1; i >= 0; --i) { if (num[i] == 0) { num[i] = 9; } else { --num[i]; break; } } if (num[0] == 0) { ans = -gao(m - 1, num + 1); } else { ans = -gao(m, num); } scanf("%s", str); m = strlen(str); transform(str, str + m, num, bind2nd(minus<char>(), '0')); ans += gao(m, num); ans = (ans % MOD + MOD) % MOD; printf("%lld\n", ans); } assert(scanf("%d", &re) == EOF); return 0; }
发表评论
-
图的割点tarjan---zoj_1119
2011-10-24 23:00 1226http://acm.zju.edu.cn/on ... -
BFS与双向BFS---zoj_1505
2011-10-09 17:14 1637http://acm.zju.edu.c ... -
静态treap+线段树---zoj_2112
2011-09-29 23:06 1702http://acm.zju.edu ... -
NIM博弈游戏,SG函数---zoj_3084,zoj_2083
2011-09-23 23:00 1312Nim游戏是两个人进行的游戏有如下规则: ... -
多重背包--zoj_2156
2011-09-14 11:10 856首先介绍经典的三种背包问题,0-1背包,完全 ... -
模式串匹配---KMP
2011-08-31 20:49 1269朴素的的模式串匹配算法通常要在向前移动文本指针 ... -
八数码问题(A*&&双向BFS)---zoj_1217
2011-08-30 22:13 1659题目地址:http://acm.zju.edu.cn/onli ... -
二分图最大匹配(匈牙利算法)--zoj1516,1525,2223
2011-07-20 22:36 1180二分图G(E,V)将点集合V分成两个部分L,R ... -
网络最大流(EK)---zoj_1734
2011-07-19 16:34 2122网络最大流是图论中的一个典型问题,为了精确的定 ... -
trie和前缀检查---zoj_2876
2011-07-13 23:03 863trie树是一种多叉树,广泛用于字典检索。如 ... -
位图bitmap
2011-07-13 21:08 908bitmap是一种广泛使用的数据结构,主要用在 ... -
LAC和RMQ的转化---zoj_3195
2011-07-12 22:35 1068我擦。。纠结了好久啊,从SF到TLE,先总结2 ... -
LAC的tarjan(离线)算法---zoj_1141
2011-07-08 17:52 1649LCA就不解释了,这里主要再次复习一下LC ... -
笛卡尔树以及treap---zoj_2243
2011-07-07 15:52 2829zoj_2243笛卡 ... -
线段染色,矩形切割,离散化---zoj_2301,zoj_1128
2011-06-24 22:32 1358染色问题:在一维坐标轴上(最右端为M),有N ... -
线段树---zoj_1610
2011-06-22 21:06 739线段树是一种二叉树的拓展,在线段树每个节点中 ... -
快速排序(qsort)
2011-06-16 17:03 773快速排序是一种高效的非稳定排序,它的基本思路 ... -
斐波那契散列
2011-06-16 16:38 3066斐波那契散列法其实是一种特殊的乘法散列,先来看乘法 ... -
强连通分支(scc)---tarjan
2011-06-15 16:17 1277本文大量 ... -
单源最短路径SPFA---zoj3146
2011-06-09 15:25 935针对Bellman-Ford算法效率比较低 ...
相关推荐
多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 dawg自动机多模式匹配 ac自动机 ...
供信息学奥林匹克竞赛选手使用 AC自动机模板
要学AC自动机需要自备两个前置技能:KMP和trie树(其实个人感觉不会kmp也行,失配指针的概念并不难) 其中,KMP是用于一对一的字符串匹配,而trie虽然能用于多模式匹配,但是每次匹配失败都需要进行回溯,如果模式串很长的话...
AC自动机算法(Aho-Corasick 多模式匹配算法)C#实现
AC自动机AC自动机AC自动机AC自动机
AC自动机算法是解决这种问题的一个经典方法,时间复杂度为O(n+m+z),其中z是T中出现的模式串的数量。AC自动机是基于keyword tree的,并对其进行一些补充。
AC自动机算法
相当给力,头文件中附带了简单的使用方法,使用istream当接口,因此你可以传入stringstream或fstream,甚至可以自己派生istream再传入,支持全文查找和增量查找两种模式,有问题可以联系我
关于AC自动机的pdf文档,很清楚的讲解了AC自动机算法及应用
BUPT 自动机实验,NFA转化DFA,java代码加实验报告
关于AC自动机的详细的讲解+标程,还有一些例题的讲解。
C语言实现,效率极高,实现了中文的关键字匹配,输出的格式为偏移量加上关键字(中文编码为GB2312)
基于单模式串和 Trie 树实现的敏感词过滤我们前面几节讲了好几种字符串匹配算法,有 BF 算法、RK 算法、BM 算法、KMP 算法,前面四种算法都是单模式串
AC自动机实现多模式串匹配,支持中文系统,同时可以支持多个模式串,测试使用Linux和Windows系统,使用20条模式串,中英文混合,测试通过
AC自动机模板,直接套,有注释N的范围,适合初学者学习
为DFA.java 中的DFA 类实现成员函数boolean recongnizeString(int move[][], int accept_state[], String word)
基于字典树的ac自动机,自己前期的实现,具有源码参考,用于查找可屏蔽应用
文学研究助手,AC自动机版本,数据结构 利用AC自动机只对文件进行一次扫描,统计要查询的单词在文档出现的次数及所在行
中文AC自动机,可以用于中文字符串,可以结合中文分词使用
编译原理的作业,有了一点数据结构的知识编的,可能有遗漏,请提点意见!