【题目链接】
【算法】
此题是AC自动机模板题
AC自动机是很神奇的算法，简单点来说，就是在一棵字典树上进行KMP，它的应用范围很广，非常实用
这篇博客写得很好，推荐阅读 ：
http://blog.csdn.net/creatorx/article/details/71100840
【代码】
个人觉得我的代码还是写得不错的，大家可以尝试阅读一下，应该可读性较高.
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; int T,N,i; char pattern[1000010],s[10010][60]; template <typename T> inline void read(T &x) { int f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; } for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; } template <typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) write(x/10); putchar(x%10+'0'); } template <typename T> inline void writeln(T x) { write(x); puts(""); } struct AC_Automation { int tot; struct node { int next[26]; int fail; int sum; } trie[5000010]; void clear() { int i; for (i = 0; i <= tot; i++) { trie[i].sum = trie[i].fail = 0; memset(trie[i].next,0,sizeof(trie[i].next)); } tot = 0; } void insert(char *s) { int i,len,root=0,x; len = strlen(s); for (i = 0; i < len; i++) { x = s[i] - 'a'; if (!trie[root].next[x]) trie[root].next[x] = ++tot; root = trie[root].next[x]; } ++trie[root].sum; } void rebuild() { int i,root,tmp; queue<int> q; q.push(0); trie[0].fail = -1; while (!q.empty()) { root = q.front(); q.pop(); for (i = 0; i < 26; i++) { if (trie[root].next[i]) { if (!root) trie[trie[root].next[i]].fail = 0; else { tmp = trie[root].fail; while (tmp != -1) { if (trie[tmp].next[i]) { trie[trie[root].next[i]].fail = trie[tmp].next[i]; break; } tmp = trie[tmp].fail; } if (tmp == -1) trie[trie[root].next[i]].fail = 0; } q.push(trie[root].next[i]); } } } } void query(char *s) { int i,x,len,tmp,p=0,ans=0; len = strlen(s); for (i = 0; i < len; i++) { x = s[i] - 'a'; while ((p != 0) && (!trie[p].next[x])) p = trie[p].fail; p = trie[p].next[x]; tmp = p; while (tmp) { if (trie[tmp].sum != 0) { ans += trie[tmp].sum; trie[tmp].sum = 0; } else break; tmp = trie[tmp].fail; } } writeln(ans); } } ACAM; int main() { read(T); while (T--) { read(N); for (i = 1; i <= N; i++) gets(s[i]); gets(pattern); ACAM.clear(); for (i = 1; i <= N; i++) ACAM.insert(s[i]); ACAM.rebuild(); ACAM.query(pattern); } return 0; }