题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2222
题意:有N(N <= 10000)个长度不超过50的模式串和一个长度不超过1e6的文本串。其中模式串可以重复。问有多少文本串在模式串中出现过。(对于相同的模式串次数仍然累加)
思路:ac自动机裸题；
KMP是先将文本串进行匹配得到失配边f[];但是并不适用于文本串较长，模式串较多的情况。因为每次查询的时间复杂度为O(n+m).n,m分别为文本串和模式串的长度；
ac自动机就是建立在Trie上，用bfs得到适配边的一个逆向过程；
即将所有的模式串建立一个状态转移，之后直接匹配文本串即可；
关键:每次看的是文本串中的当前点的后缀是那个模式串的前缀，(BFS中获得f[]的关键思想)或者就是那个模式串。之后递归打印即可；
// 358MS 32704K
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> #include<map> #include<queue> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define MSi(a) memset(a,0x3f,sizeof(a)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 typedef pair<int,int> PII; #define A first #define B second #define MK make_pair typedef __int64 ll; template<typename T> void read1(T &m) { T x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} m = x*f; } template<typename T> void read2(T &a,T &b){read1(a);read1(b);} template<typename T> void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);} template<typename T> void out(T a) { if(a>9) out(a/10); putchar(a%10+'0'); } int T,kase = 1,i,j,k,n,m; const int sigma_size = 26; const int maxn = 10000*50+7; struct Aho_Corasick{ int ch[maxn][sigma_size]; int val[maxn],f[maxn],last[maxn],cnt[maxn]; int sz; map<string,int> ms; Aho_Corasick(){} void init(){sz = 1; MS0(ch[0]);MS0(cnt);ms.clear();} void Insert(char *s,int v){ int u = 0,n = strlen(s); for(int i = 0;i < n;i++){ int c = s[i] -'a'; if(!ch[u][c]){ MS0(ch[sz]); val[sz] = 0; ch[u][c] = sz++; } u = ch[u][c]; } val[u] = v; ms[string(s)] = v;//使用map来对应重复出现的字符串;竟然可以强转.. } void getFail(){ queue<int> q; f[0] = 0; //初始化队列 for(int c = 0;c < sigma_size;c++){ int u = ch[0][c]; if(u) { f[u] = 0; q.push(u); last[u] = 0;} } while(!q.empty()){ int r = q.front();q.pop(); for(int c = 0;c < sigma_size;c++){ int u = ch[r][c]; if(!u) {ch[r][c] = ch[f[r]][c]; continue;}//实现压缩 q.push(u); int v = f[r]; while(v && !ch[v][c]) v = f[v]; f[u] = ch[v][c]; last[u] = val[f[u]]?f[u]:last[f[u]]; } } } //从文本串中找模板; void Find(char *T){ int n = strlen(T); int j = 0; for(int i = 0;i < n;i++){ int c = T[i] - 'a'; j = ch[j][c];//直接查找即可; if(val[j]) print(j); else if(last[j]) print(last[j]); } } void print(int j){ if(j) { cnt[val[j]]++; print(last[j]); } } }ac; char p[10007][55]; char text[1000007]; int main() { read1(T); while(T--){ ac.init(); read1(n); rep1(i,1,n){ scanf("%s",p[i]); ac.Insert(p[i],i); } ac.getFail(); scanf("%s",text); ac.Find(text); int ans = 0; rep1(i,1,n){ if(ac.cnt[ac.ms[string(p[i])]]) ans++; } out(ans); puts(""); } return 0; }