注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1966][Ahoi2005]VIRUS 病毒检测  

2015-01-03 18:46:35|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1966: [Ahoi2005]VIRUS 病毒检测

BZOJ上缺失的部分:
字符串个数N<500,每个串长度<500

不会做……看题解发现N^3能过……
吓得我尿都出来了
然后我的做法好像比较蛋疼和网上的题解不太一样……
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
#include<bitset>
using namespace std;
const int N = 1000+100;
typedef long long ll;
int n,m,ans,T,len;
char tmp[N],str[N];
short bh[500];
bitset<N> v[N*350];
struct Node{
Node(){memset(ch,0,sizeof(ch));cot=0;d=++T;}//printf("[%d]",d);}
int cot,d;
Node *ch[4];
};
typedef pair<Node*,int> Data;
queue<Data>dui;
struct AC{
Node*ROOT;
AC(){ROOT = new Node();}
void insert(char str[],int len){
Node *r = ROOT;
for(int i=1;i<=len;i++){
int d = bh[str[i]];
if(!r->ch[d])r->ch[d] = new Node();
r = r->ch[d];
}r->cot++;
}
void push(Node *r,int b){
if(r==NULL || b > len)return;
int a = r->d;
if(!v[a][b]){
v[a][b] = 1;
dui.push(Data(r,b));
}
}
void solve(){
dui.push(Data(ROOT,0));
v[1][0] = 1;
int c;
while(!dui.empty()){
Data NOW = dui.front();dui.pop();
Node *r = NOW.first;int now = NOW.second;
//printf("[%d %d]\n",r->d,now);
//this is *
if(str[now]=='*')
for(int i=0;i<4;i++)push(r->ch[i],now);
if(now == len){
ans += r->cot;
r->cot = 0;
continue;
}
//next
if((c = bh[str[now+1]])>=0){
push(r->ch[c],now+1);
}else{
for(int i=0;i<4;i++)push(r->ch[i],now+1);
if(str[now+1] == '*')push(r,now+1);
}
}
}
}ac;
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
//freopen("in.txt","r",stdin);
//printf("%f\n",sizeof(v)/1024.0/1024);
int i,j;
//printf("%d %d\n",'?','*');
bh['A'] = 0;bh['C'] = 1;
bh['T'] = 2;bh['G'] = 3;
bh['?'] = -1;bh['*'] = -2;
scanf("%s",str+1);
len = strlen(str+1);
str[0]='?';
n = scan();
for(i=1;i<=n;i++){
scanf("%s",tmp+1);
//printf("\n");
j = strlen(tmp+1);
ac.insert(tmp,j);

}
ac.solve();
printf("%d\n",n-ans);
return 0;
}

题解:
Trie树+Bfs
把那一堆字符串建一棵trie树,然后在上面匹配带通配符的串,特别处理一下'*'和'?'。
最后再加个判重,当到末尾节点的时候把ans加上以这个结尾的字符串个数,并且把这个个数再设为0(防止重复)。
Trie树节点个数<N*N 每个点匹配的位置可能个数是N,总时间复杂度是N^3。
注意判重的数组要用bitset否则会MLE= =、

网上题解说是AC自动机?这不是胡扯淡么……连失配边都没有叫AC自动机?
大概是我不明白是怎么做的。。
  评论这张
 
阅读(123)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017