2017西安交大ACM小学期 文本查找[AC自动机]

文本查找

发布时间: 2017年7月5日 00:10   最后更新: 2017年7月5日 13:47   时间限制: 1500ms   内存限制: 128M

描述

给定m种两两不同的关键词，并给定一段文本，问这段文本中有几种关键词出现（一种关键词出现多次只算一次）。

输入

多组输入数据。 每组数据第一行一个正整数 m ，表示有 m 个关键词。 接下来 m 行每行一个关键词，关键词仅包含小写字母。 最后一行为文本，仅包含小写字母。 每组数据保证关键词总长度不超过 106 ，文本不超过 106 。 总字符输入量不超过 107 。

输出

对于每组数据，输出一行一个整数，表示答案。

样例输入1  复制 3 a aa b aa 样例输出1 2 AC自动机的裸题，这里要说明的一点就是，一种关键词出现多次只能算一次，这样的话，我们就可以在一个关键词匹配完成后，在Trie树相关位置打上一个标记，防止下次重复计数。

代码:

#include <cstdio> #include <cstring> #include <queue> using namespace std; const int MAXN = 1e6+7;; #define LETTER 26 struct Trie{ int num, fail,match; int next[LETTER]; }pool[MAXN]; Trie* const trie = pool + 1; int cnt; void init(){ cnt = 0; memset(pool, 0, 2 * sizeof(Trie)); trie[0].fail = -1; } inline int convert(char c){ return c - 'a'; } void build() { queue<int> q; q.push(0); while (!q.empty()){ int t = q.front(); q.pop(); for (int i = 0; i < LETTER; i++){ int &cur = trie[t].next[i]; if (cur){ q.push(cur); trie[cur].fail = trie[trie[t].fail].next[i]; trie[cur].match = trie[cur].num ? cur :trie[trie[cur].fail].match; } else cur = trie[trie[t].fail].next[i]; } } } int search(char *s) { int ret = 0, cur = 0; for (int i = 0; s[i]; i++){ cur = trie[cur].next[convert(s[i])]; for (int temp = trie[cur].match; temp;temp = trie[trie[temp].fail].match){ ret += trie[temp].num; if(!trie[temp].num) break; trie[temp].num = 0; } } return ret; } void insert(char s[]){ int cur = 0; for(int i = 0;s[i];i++){ int &pos = trie[cur].next[convert(s[i])]; if(!pos){ pos = ++cnt; memset(&trie[cnt],0,sizeof(Trie)); } cur = pos; } trie[cur].num ++; } char pat[MAXN]; char str[MAXN]; int main(){ int m; while(~scanf("%d",&m)){ init(); while(m--){ scanf(" %s",pat); insert(pat); } build(); scanf(" %s",str); int ans = search(str); printf("%d\n",ans); } }