fzoj 2005 Computer Virus on Planet Pandora 福州现场赛

    技术2022-05-13  7

    http://acm.fzu.edu.cn/problem.php?pid=2005

    这题。。。不想说了,当时居然没把题目意思搞清楚

    The length of the program is at least 1 and at most 5,100,000, no matter in the compressed format or after it is decompressed to original format.

    这句话,我干,我想对出题人说,能不能不要用那么模糊的词,本来大家都的英语都不是专业的,还搞成这样。

    当时比赛的时候我们就理解成不管压不压缩他的长度都有可能达到5100000,结果最后各种去对pattern strings做处理,各种处理md

    昨天听他们说了下,就是一个裸的AC自动机,我当时那个崩溃啊,听到他们说那句话是说的总长度,我更崩溃。。。md鄙视出题的人。

    发泄完了,我没有攻击出题人的意思,也怪我们英语不好,理解错了,只是小发泄一下,不然我们就能多一个题啊。。。

    说了这么多,下面说下这个题:其实题目很简单,就是一个最简单的AC自动机,字需要处理一下,文章,把那个字符串的[]去掉,全部展开,然后正着查一次,反着查一次。

    其实很简单!!!

    有人说网上的模板有问题,不过我到没发现有什么问题,其实有个地方是有点差别,我写在代码注释里

    /* * File: main.cpp * Author: Mi * * Created on 2011年3月31日, 下午8:16 */ #include <cstdlib> #include <stdio.h> #include <string.h> #include <algorithm> #define KIND 26 #define MAX 250*1000+10 #define MAXN 5100010 using namespace std; /* * */ char msg[MAXN],msgt[MAXN]; struct node { node *fail; node *next[KIND]; bool isword; int cnt; node() { fail=NULL; memset(next,NULL,sizeof(next)); isword=false; cnt=0; } }*que[MAX],*root; void Insert(char *s) { int l=strlen(s); node *p=root; for(int i=0;i<l;i++) { int index=s[i]-'A'; if(p->next[index]==NULL) p->next[index]=new node; p=p->next[index]; } p->isword=true; p->cnt++; } void Build_AC_Automation() { int tail=0,head=0; que[head++]=root; root->fail=NULL; while(tail!=head) { node *cur=que[tail++]; for(int i=0;i<KIND;i++) if(cur->next[i]!=NULL) { if(cur==root) cur->next[i]->fail=root; else { node *ptr=cur->fail; while(ptr!=NULL) { if(ptr->next[i]!=NULL) { cur->next[i]->fail=ptr->next[i]; if(ptr->next[i]->isword)//就是这两句,如果fail指向的next[i]是个单词的话,那么cur->next[i]也改成一个单词,据说可以提速但是没感觉到 cur->next[i]->isword=true;//想想很容易理解 break; } ptr=ptr->fail; } if(ptr==NULL) cur->next[i]->fail=root; } que[head++]=cur->next[i]; } } } int AC_search() { int ans=0,l=strlen(msg); node *ptr=root; for(int i=0;i<l;i++) { int index=msg[i]-'A'; while(ptr->next[index]==NULL&&ptr!=root) ptr=ptr->fail; ptr=ptr->next[index]; if(ptr==NULL) ptr=root; node *temp=ptr; while(temp!=NULL&&temp->cnt!=-1) { ans+=temp->cnt; temp->cnt=-1; temp=temp->fail; } } return ans; } int main(int argc, char** argv) { int t,n; scanf("%d",&t); while(t--) { scanf("%d",&n); root=new node; for(int i=0;i<n;i++) { char s[1005]; scanf("%s",s); Insert(s); } Build_AC_Automation(); scanf("%s",msgt); int k=0,l=strlen(msgt); for(int i=0;i<l;i++) { if(msgt[i]=='[') { int j=i+1; while(msgt[j]>=0&&msgt[j]<='9') j++; char str[1005]; strncpy(str,msgt+i+1,j-i); str[j-i]='/0'; int cnt=atoi(str); for(int h=0;h<cnt;h++,k++) msg[k]=msgt[j]; i+=(strlen(str)+1); } else msg[k++]=msgt[i]; } msg[k]='/0'; // puts(msg); int ans=0; ans+=AC_search(); reverse(msg,msg+strlen(msg)); ans+=AC_search(); printf("%d/n",ans); } return 0; }


    最新回复(0)