首页 > 代码库 > Zoj 3430 Detect the Virus (AC自动机)
Zoj 3430 Detect the Virus (AC自动机)
题目大意:
给出来n条64base的病毒编码序列。
再给出m条模式串,让你反编码之后求出里面包含多少病毒序列。
思路分析:
很裸的AC自动机了。但是各种恶心。
动态开trie 静态开queue 就会RE。
全部动态开辟就会MLE。
各种姿势之后静态开trie 动态开queue才能AC。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <queue> #define maxn 50005 using namespace std; const char tab = 0; const int max_next = 256; int tlen=0; int next[maxn][max_next],fail[maxn],num[maxn],mark[maxn],siz; int rev[300]; int newnode() { for(int i=0;i<max_next;i++) next[siz][i]=0; fail[siz]=num[siz]=mark[siz]=0; return siz++; } void Insert(int *s,int len) { int p=0; for(int i=0;i<len;i++) { int &x=next[p][s[i]]; p=x?x:x=newnode(); } num[p]++; } void acbuild() { queue<int>Q; Q.push(0); while(!Q.empty()) { int temp=Q.front(); Q.pop(); for(int i=0;i<max_next;i++) { int v=next[temp][i]; if(v==0)next[temp][i]=next[fail[temp]][i]; else Q.push(v); if(temp!=0)fail[v]=next[fail[temp]][i]; } } } int query(int *s,int len,int id) { int cnt=0; for(int i=0,p=0;i<len;i++) { p=next[p][s[i]]; for(int f=p;f&&mark[f]!=id;f=fail[f]){ mark[f]=id; if(num[f]>0)cnt++; } } return cnt; } int word[10005]; void ReEncode(char *a){ tlen=0; for(int i=0,len=0,x=0;a[i] && a[i] != '=';++i){ len+=6,x=(x<<6)|rev[a[i]]; if(len>=8){ word[tlen++]=(x>>(len-8))&0xff; len-=8; } } } char tmp[10005]; int main() { for(int i=0;i<26;i++) rev[i+'A']=i; for(int i=26;i<52;i++) rev[i+'a'-26]=i; for(int i=52;i<62;i++) rev[i+'0'-52]=i; rev['+']=62; rev['/']=63; int n; while(scanf("%d",&n)!=EOF) { siz=0; newnode(); for(int i=1;i<=n;i++) { scanf("%s",tmp); ReEncode(tmp); Insert(word,tlen); } acbuild(); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",tmp); ReEncode(tmp); printf("%d\n",query(word,tlen,i)); } puts(""); } return 0; }
Zoj 3430 Detect the Virus (AC自动机)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。