本文主要是介绍ZOJ 3430 Pizza schedule，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给你一串编码后的单词和一篇文章 问 编码前文章中出现了几个单词
思路：
根据题意反编码 然后AC自动机跑一下
转化字符时候注意长度 因为可能转换出'\0' 所以转完后再求strlen会出错
注意 ZOJ的char默认是signed char 所以转码后要么存在unsigned char数组里 要么用int数组存 否则会错的！！ 因为signed char无法表示128+的数字！！
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 51200
#define M 260int n,m,tot,res;
struct node
{int next[M];int cnt,fail,vis;void init(){memset(next,-1,sizeof(next));fail=cnt=vis=0;}
}nd[N];
int qu[N];
int head,tail;
char word[N];
int code[N];void mf()
{int i,j,idx,fa;head=tail=0;for(i=0;i<M;i++){if(nd[0].next[i]!=-1)qu[tail++]=nd[0].next[i];}while(head<tail){fa=qu[head++];for(i=0;i<M;i++){if(nd[fa].next[i]!=-1){qu[tail++]=nd[fa].next[i];idx=nd[fa].fail;while(idx>0&&nd[idx].next[i]==-1) idx=nd[idx].fail;if(nd[idx].next[i]!=-1) idx=nd[idx].next[i];nd[nd[fa].next[i]].fail=idx;}}}
}void fd(int len)
{int i,idx,trvl;for(i=idx=0;i<len;i++){while(idx>0&&nd[idx].next[code[i]]==-1) idx=nd[idx].fail;if(nd[idx].next[code[i]]!=-1){trvl=idx=nd[idx].next[code[i]];while(trvl>0&&nd[trvl].vis!=-1){if(nd[trvl].cnt) res+=nd[trvl].cnt;nd[trvl].vis=-1;trvl=nd[trvl].fail;}}}
}int bin[N*10];
int change()
{int i,j,k,len,tmp;len=strlen(word);for(i=k=0;i<len;i++){if(word[i]=='='){k-=2;continue;}if(word[i]>='A'&&word[i]<='Z') tmp=word[i]-'A';else if(word[i]>='a'&&word[i]<='z') tmp=word[i]-'a'+26;else if(word[i]>='0'&&word[i]<='9') tmp=word[i]-'0'+52;else if(word[i]=='+') tmp=62;else if(word[i]=='/') tmp=63;for(j=5;j>=0;j--){if(tmp&(1<<j)) bin[k++]=1;else bin[k++]=0;}}for(i=len=0;i<k;i+=8){for(j=i,tmp=0;j<i+8;j++) tmp=(tmp<<1)|bin[j];code[len++]=tmp;}return len;
}int main()
{int i,len,j,idx;while(~scanf("%d",&n)){tot=0;nd[0].init();for(i=1;i<=n;i++){scanf("%s",word);len=change();for(j=idx=0;j<len;j++){if(nd[idx].next[code[j]]==-1){nd[idx].next[code[j]]=++tot;nd[tot].init();}idx=nd[idx].next[code[j]];}nd[idx].cnt++;}mf();scanf("%d",&m);for(i=1;i<=m;i++){res=0;scanf("%s",word);len=change();fd(len);printf("%d\n",res);for(j=0;j<=tot;j++) nd[j].vis=0;}puts("");}return 0;
}这篇关于ZOJ 3430 Pizza schedule的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
