栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 3430 Detect the Virus

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 3430 Detect the Virus

#include <iostream>#include <string>#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>#include <vector>#include<map>#define MAX(a,b) ((a)>(b)?(a):(b))#define MIN(a,b) ((a)<(b)?(a):(b))#define CL(a,b) memset(a,b,sizeof(a))#define LL long long int#define N 35500#define mod 1000000007#define inf 1000000000using namespace std;char hash[66][10];int change[300];void init(){int i,j,k;for(i=0;i<26;i++){change[i+'A']=i;change[i+'a']=i+26;}for(i=0;i<10;i++)change[i+'0']=i+52;change['+']=62;change['/']=63;for(i=0;i<64;i++){k=i;for(j=5;j>=0;j--){hash[i][j]=(k&1)+'0';k>>=1;}hash[i][6]='';}}struct data{int next[256],fail;int val;void init(){CL(next,0);fail=0;val=-1;}}tree[N];int all,q[N];void insert(int *s,int len){int p=0,k,i=0;while(s[i]!=-1){k=s[i];if(tree[p].next[k]==0){tree[p].next[k]=++all;tree[all].init();}p=tree[p].next[k];i++;}tree[p].val=len;}void build_ac(){int head,tail,p,t,i,j,k;head=tail=0;q[head++]=0;while(head!=tail){t=q[tail++];for(i=0;i<256;i++){p=tree[t].next[i];if(p==0)tree[t].next[i]=tree[tree[t].fail].next[i];elseq[head++]=p;if(p&&t){tree[p].fail=tree[tree[t].fail].next[i];}}}}int bits[N*10];int s[N];int getval(char *str){int len,i,j,k;len=strlen(str);k=0;for(i=0;i<len;i++){if(str[i]=='=')break;else{for(j=0;j<6;j++)bits[k++]=hash[change[str[i]]][j]-'0';}}int v=k;if(i==len-1&&str[i]=='=')k-=2;if(i==len-2&&str[i]=='='&&str[i+1]=='=')k-=4;int val=0;len=0;for(i=0;i<k;i+=8){val=0;for(j=i;j<i+8;j++){val=val*2+bits[j];}s[len++]=val;}for(i=0;i<v;i++)bits[i]=0;s[len]=-1;return len;}char str[N];int h[600];void sovle(int len){int i;int p=0;for(i=0;i<len;i++){p=tree[p].next[s[i]];int t=p;while(true){if(tree[t].val!=-1)h[tree[t].val]++;if(t==0)break;t=tree[t].fail;}}}int main(){int n;int i,j,k,len;init();while(scanf("%d",&n)!=EOF){int cas=0;CL(bits,0);all=0;tree[0].init();for(cas=0;cas<n;cas++){scanf("%s",str);getval(str);insert(s,cas);}build_ac();int m;scanf("%d",&m);memset(h,0,sizeof(h));for(cas=0;cas<m;cas++){scanf("%s",str);int len=getval(str);sovle(len);int sum=0;for(i=0;i<n;i++){if(h[i]!=0){sum++;h[i]=0;}}printf("%dn",sum);}printf("n");}}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/372957.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号