|算法讨论|AC自动机学习笔记

2019-11-11 04:58:40

字体：大中小

来源：转载

供稿：网友

~~在学习AC自动机之前需要熟练掌握WA自动机、RE自动机与TLE自动机~~

模板题：Hdu 2222 KeyWords Search，解决先给出关键字后，再给出寻找文本进行匹配问题

#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define ms(i,j) memset(i,j, sizeof i); using namespace std;const int MAXN = 10000 + 5, _SIZE = 26; int n;struct acam{ int sz;//结点编号 int res; int ch[MAXN*51][_SIZE];//Tire int last[MAXN*51];//后缀链接 int f[MAXN*51];//失配函数 int val[MAXN*51][2];//结点的权值 bool used[MAXN*51];//用过 void init()//初始化 { ms(val,0); ms(ch,0); ms(used,false); sz = 1; res = 0; } void insert(char *s, int v)//插入一个模板 { int u = 0; int len = strlen(s); for (int i=0;i<len;i++) { int c = s[i] - 'a'; if (ch[u][c]) { u = ch[u][c]; } else { ch[u][c] = ++sz; u = ch[u][c]; } if (i==len-1) { val[u][0] = v; val[u][1]++; } } } void g(int j)//递归更新cnt { if (j&&!used[val[j][0]]) { res+=val[j][1]; used[val[j][0]] = true; g(last[j]); } } void find(char *T)//在T中匹配 { int len = strlen(T); int j = 0; for (int i=0;i<len;i++) { int c = T[i] - 'a'; j = ch[j][c]; if (val[j][0]) g(j); else if (last[j]) g(last[j]); } } void getFail()//获得失配函数 { queue<int> q; f[0] = 0; for (int c=0;c<_SIZE;c++)//初始化进队 { int u = ch[0][c]; if (u) { q.push(u); f[u] = 0; last[u] = 0; } } while (!q.empty()) { int r = q.front(); q.pop(); for (int c=0;c<_SIZE;c++) { int u = ch[r][c]; if (!u) { ch[r][c] = ch[f[r]][c]; continue; } q.push(u); int j = f[r]; while (j&&!ch[j][c]) j = f[j]; f[u] = ch[j][c]; last[u] = (val[f[u]][0]) ? (f[u]) : (last[f[u]]); } } } }ac;char s[1000000 + 5];int main() { int kase; scanf("%d", &kase); while (kase--) { ac.init(); scanf("%d", &n); for (int i=1;i<=n;i++) { scanf("%s", s); ac.insert(s,i); } scanf("%s", s); ac.getFail(); ac.find(s); PRintf("%d/n", ac.res); } return 0; }

上一篇：1.JUCE——入门

下一篇：基础练习高精度加法