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

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

POJ 4052 Hrinity  

2012-05-14 19:48:39|  分类: 字符串 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       这题现场赛搞了一个小时还是以WA饮恨收场,回来之后查了半天也没搞明白自己哪错了,最后向羊神请教了一下才发现我对题意的理解有点小问题,所以才WA到死。而后改了改很快就过了。做法就是用AC自动机暴力把所有的出现的子串先标记出来,然后再对每个子串进行暴力去重。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
#include<cstring>
#include<string>
#define N 26
using namespace std;
struct trie{
int next[N],fail;
int tag;
}data[1000000];
int inp;
bool vis[1000000],ok[2509],flag[2509];
int n;
char str[2509][1200];
char art[5100009];
string ts;
int init(int a){
memset(data[a].next,0,sizeof(data[a].next));
data[a].fail=data[a].tag=0;
vis[a]=0;
return a;
}
void ac_insert(char *a,int v){
int p=0;
for(;*a;a++){
int d=*a-'A';
if(data[p].next[d]==0 ) data[p].next[d]=init(++inp);
p=data[p].next[d];
}
data[p].tag=v;
}
void ac_bfs(void){
queue<int> que;
for(int i=0;i<N;i++)
if(data[0].next[i]) que.push(data[0].next[i]);
while(que.size()){
int p=que.front();
for(int i=0;i<N;i++){
int temp=data[p].next[i];
if(temp){
que.push(temp);
data[temp].fail=data[data[p].fail].next[i];
}
else
data[p].next[i]=data[data[p].fail].next[i];
}
que.pop();
}
}
void init_flag(char *s,int id){
int p=0;
for(;*s;s++){
p=data[p].next[*s-'A'];
for(int i=p;i;i=data[i].fail)
if(data[i].tag!=id)
flag[data[i].tag]=false;
}
}
void decode(char *s){
for(int i=0;ts[i];i++){
if(ts[i]=='['){
int q=0;
for(i++;isdigit(ts[i]);i++) q=q*10+ts[i]-'0';
while(q--) *s++=ts[i];
i++;
}
else
*s++=ts[i];
}
*s='\0';
}
void search(char *s){
int p=0;
for(;*s;s++){
p=data[p].next[*s-'A'];
for(int i=p;i&&!vis[i];i=data[i].fail)
ok[data[i].tag]=true,vis[i]=1;
}
}
int main(){
//freopen("in.in","r",stdin);
int T;
cin>>T;
while(T--){
init(inp=0);
memset(ok,false,sizeof(ok));
cin>>n;
for(int i=1;i<=n;i++){
cin>>ts;
decode(str[i]);
ac_insert(str[i],i);
}
ac_bfs();
cin>>ts;
decode(art);
search(art);
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) flag[i]=ok[i];
for(int i=1;i<=n;i++)
if(ok[i])
init_flag(str[i],i);
int ans=0;
for(int i=1;i<=n;i++)
ans+=flag[i];
cout<<ans<<endl;
}
}


  评论这张
 
阅读(260)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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