链接：点击打开链接
题意：给出一个字典和一个模式串，问模式串是否出现字典中的单词
代码：
#include <queue> #include <vector> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; const int siz=1000005; struct node{ int c[26]; int dis,fail; }s[siz]; int rt; void in(char ss[]){ int i,u; u=0; for(i=0;ss[i];i++){ if(s[u].c[ss[i]-'a']==0) s[u].c[ss[i]-'a']=rt++; u=s[u].c[ss[i]-'a']; } s[u].dis=1; } void getfail(){ int u,v,i,j,tmp; queue<int> qu; qu.push(0); while(qu.size()){ u=qu.front(); qu.pop(); for(i=0;i<26;i++){ if(v=s[u].c[i]){ if(u==0) s[v].fail=0; else{ tmp=s[u].fail; while(tmp&&s[tmp].c[i]==0){ tmp=s[tmp].fail; } s[v].fail=s[tmp].c[i]; s[v].dis+=s[s[tmp].c[i]].dis; } //找fail的同时，将个数也进行转移 qu.push(v); } } } } int ac(char ss[]){ int i,j,u,v; u=0; getfail(); for(i=0;ss[i];i++){ while(u&&s[u].c[ss[i]-'a']==0) u=s[u].fail; u=v=s[u].c[ss[i]-'a']; //因为个数也进行了转移，所以直接在trie树上跑即可 if(s[u].dis) return 1; } return 0; } int main(){ int n,i,j; char ss[siz]; while(scanf("%d",&n)!=EOF){ rt=1; memset(s,0,sizeof(s)); for(i=1;i<=n;i++){ scanf("%s",ss); in(ss); } scanf("%s",ss); if(ac(ss)) puts("YES"); else puts("NO"); } return 0; }