hdu 3065 病毒侵袭持续中（AC automaton)

hdu 3065 病毒侵袭持续中（AC automaton)

题目：​​例如：

Sample Input

3 AA BB CC ooxxCC%dAAAoen....END

Sample Output

Hint

AC自动机模板中的insert函数代码p->sum++;统计的是子串出现的次数（可能出现相同的子串，那时sum就大于1了）。本题的子串每个只出现一次，需要找到在源码串中每个子串出现的次数，且要输出对应的子串。所以要建立好字符串和结点的映射关系。输出的sum也要灵活处理。事实上，tag的是否标记就决定了源码串中子串是否可以重叠，标记了则不可以重叠，没有标记则能重叠。话说回来，AC自动机应该是我见过比较耗内存的算法，每次提交都和内存限制有个亲密的接触。

#include #include#include#include#includeusing namespace std;int head,tail;const int nn=60; //122-65=57int N;char str[2000010],keyword[55]; char s[1000][55];struct node{ int sum,id; node *next[nn],*fail; bool operator <(const node other)const { return id>other.id; } node(){ //inital node fail=NULL; id=sum=0; memset(next,0,sizeof(next)); //here }}*q[55*1000];node *root;void insert_t(char str[],int dex){ int temp,len; node *p=root; len=strlen(str); for(int i=0;inext[temp]==NULL)p->next[temp]=new node(); p=p->next[temp]; } p->id=dex; strcpy(s[dex],str); p->sum++;}void build_ac(){ //inital fail point q[tail++]=root; while(headnext[i]!=NULL){ if(p==root)p->next[i]->fail=root; else { temp=p->fail; while(temp){ if(temp->next[i]){ p->next[i]->fail=temp->next[i]; break; } temp=temp->fail; } if(!temp)p->next[i]->fail=root; } q[tail++]=p->next[i]; } } }}priority_queue que;void query(){ int i,dex,len=strlen(str); node *p=root; for(i=0;i57){ p=root; continue; } while(p->next[dex]==NULL&&p!=root)p=p->fail; p=p->next[dex]; if(!p)p=root; node *temp=p; while(temp!=root&&temp->sum!=0){ que.push(*temp); temp=temp->fail; } }}int main(){ int t; while(cin>>N){ head=tail=0; root=new node(); int i,j,total=0; for(i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。