HDU 2896 病毒侵袭 AC自动机

我表示不是很懂HDU卡内存的优良传统.......以及他们卡输出的良好风尚........

AC自动机裸体关键在于http://ascii.911cha.com/

#include<cstring> #include<cstdio> #include<vector> #include<iostream> #include<algorithm> using namespace std; struct Trie {Trie *ch[95],*fail,*last;int who,had;Trie(){memset(ch,0,sizeof(ch));fail=last=NULL;who=had=0;} }*root,*q[70005]; int n,m; char c[200],w[10005]; inline void insert(char *s,int x) {int len=strlen(s);Trie *now=root;for(int i=0;i<len;i++){if(now->ch[s[i]-32]==NULL)now->ch[s[i]-32]=new Trie();now=now->ch[s[i]-32];}now->who=x; } inline void build() {q[0]=root;for(int i=0,j=0;i<=j;i++)for(int l=0;l<95;l++)if(q[i]->ch[l]){Trie *now=q[i]->fail;while(now&&!now->ch[l])now=now->fail;q[++j]=q[i]->ch[l];q[j]->fail=now?now->ch[l]:root;q[j]->last=q[j]->who?q[j]:q[j]->fail->last;}elseq[i]->ch[l]=q[i]==root?root:q[i]->fail->ch[l]; } inline void Init() {root=new Trie();scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",c);insert(c,i);}build(); } vector<int> have; int ans; inline void job(int x) {scanf("%s",w);int len=strlen(w);have.clear();Trie *now=root;for(int i=0;i<len;i++){now=now->ch[w[i]-32];for(Trie *Now=now->last;Now;Now=Now->last)if(Now->had!=x)have.push_back(Now->who),Now->had=x;elsebreak;}if(have.empty())return;printf("web %d:",x);ans++;sort(have.begin(),have.end());for(int j=0;j<have.size();j++)printf(" %d",have[j]);printf("\n"); } inline void work() {scanf("%d",&m);for(int i=1;i<=m;i++)job(i); } inline void print() {printf("total: %d\n",ans); } int main() {Init(); work();print();return 0; }

 

转载于:https://www.cnblogs.com/TSHugh/p/7131565.html

总结

以上是生活随笔为你收集整理的HDU 2896 病毒侵袭 AC自动机的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。