zoj3430Detect the Virus(ac自动机)

链接

解码之后是跟普通的自动机求解一下的,只不过解码比较恶心,512=》N》=0 ,所以不能用字符串来存,需要转换成整数来做。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 53769
#define NN 15010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
const int child_num = ;
char s[NN],vir[NN];
int di[NN*],od[NN],vv[NN];
bool f[N];
class ACAutomation
{
private:
int ch[N][child_num];
int val[N];
int fail[N];
int Q[N];
int id[];
int sz;
// int dp[2][N][1<<10];
public:
void init()
{
fail[] = ;
for(int i = ; i < child_num; i++)
id[i] = i;
}
void reset()//初始化
{
memset(ch[],,sizeof(ch[]));
memset(val,,sizeof(val));
sz = ;
}
void insert(int *a,int key,int k)//建立trie树
{
int p = ;
for( int i = ; i < k ; i++)
{
int c = id[a[i]];
if(ch[p][c]==)
{
memset(ch[sz],,sizeof(ch[sz]));
ch[p][c] = sz++;
}
p = ch[p][c];
}
val[p] += key;
}
void construct()//构建fail指针
{
int head = ,tail = ,i;
for(i = ;i < child_num ; i++)
{
if(ch[][i])
{
fail[ch[][i]] = ;
Q[tail++] = ch[][i];
}
}
while(head!=tail)
{
int u = Q[head++];
for(i = ;i < child_num ;i ++)
{
if(ch[u][i]!=)
{
Q[tail++] = ch[u][i];
fail[ch[u][i]] = ch[fail[u]][i];
}
else
ch[u][i] = ch[fail[u]][i];
}
}
}
int work(int *s,int k)
{
int p = ,ans = ;
memset(f,,sizeof(f));
for(int i = ; i < k ; i++)
{
int d = id[s[i]];
p = ch[p][d];
int tmp = p;
while(tmp!=&&!f[tmp])
{
ans+=val[tmp];
f[tmp] = ;
tmp = fail[tmp];
}
}
return ans;
}
}ac;
int change(char *a)
{
int i,k = strlen(a),j;
int g = ,gg,num = ;
for(i = ;i < k ; i++)
{
if(a[i]=='=')
{
num++;
continue;
}
int x = od[a[i]];gg=;
for(j=;j>=;j--)
{
di[g++]=((x&(<<j))>);
}
}
if(num==)
g-=;
else if(num==)
g-=;
gg = ;
int y = ;
for(j = ;j < g ; j++)
{
y+=di[j]*(<<(-j%));
if((j+)%==)
{
vv[gg++] = y;
y = ;
}
}
return g/;
}
int main()
{
int n,i,m;
for(i = 'A' ; i <= 'Z' ; i++)
od[i] = i-'A';
for(i = 'a' ; i <= 'z' ; i++)
od[i] = +i-'a';
for(i = ''; i <= '' ; i++)
od[i] = +i-'';
od['+'] = ,od['/'] = ;
ac.init();
while(scanf("%d",&n)!=EOF)
{
ac.reset();
for(i = ; i <= n; i++)
{
scanf("%s",vir);
int len = change(vir);
ac.insert(vv,,len);
}
ac.construct();
scanf("%d",&m);
for(i = ; i <= m ;i++)
{
scanf("%s",s);
int len = change(s);
printf("%d\n",ac.work(vv,len));
}
puts("");
}
return ;
}
上一篇:有多个正整数存放在数组中,编写一个函数要求偶数在左边由小到大顺序放置,奇数在右边,也是由小到大顺序放置,Java实现


下一篇:一款Java开源的Springboot即时通讯 IM,附源码