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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1030] [JSOI2007]文本生成器  

2014-05-08 11:53:20|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
@[BZOJ1030] [JSOI2007]文本生成器

AC自动机+DP

对着laingjs神犇的标程写了好长时间Q.Q

果然我对字符串匹配什么还是有点晕恩....

因为是全程指针所以记忆化的地方比较奇怪

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
const int MOD = 10007;
using namespace std;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\n'||cc=='\r')cc=getchar();
if(cc=='+'){fh=1;cc=getchar();}
if(cc=='-'){fh=-1;cc=getchar();}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
int scans(char s[]){
char cc=' ';int i;
while(cc==' '||cc=='\n'||cc=='\r')cc=getchar();
for(i=1;'A'<=cc&&cc<='Z';i++){
s[i]=cc;
cc=getchar();
}
return i-1;
}
struct Node{
int f[101];bool end;
Node *ch[26],*fail,*next[26];
Node(){end=0;memset(next,0,sizeof(next));memset(ch,0,sizeof(ch));fail=NULL;memset(f,-1,sizeof(f));}
}house[100000],*ROOT;
queue <Node *>dui;
int n,m,top;
Node *newNode(){
if(top<100000) return &house[top++];
return new Node();
}
int dp(int len,Node *r){
for(Node *l=r;l!=ROOT;l=l->fail)//之前忘记加这个
if(l->end) return 0;
if(len==m) return 1;
if(r->f[len]!=-1) return r->f[len];
int ans=0;
for(int i=0;i<26;i++)
ans=(ans+dp(len+1,r->next[i]))%MOD;
return r->f[len]=ans;
}
int pow(int a,int k){
int re=1;
for(;k;k>>=1,a=(a*a)%MOD)
if(k&1) re=(re*a)%MOD;
return re;
}
int main(){
//freopen("input.txt","r",stdin);
int i,j;
char str[100+1];
n=scan();m=scan();
ROOT=newNode();
for(i=1;i<=n;i++){
int len=scans(str);
Node *r = ROOT;
for(j=1;j<=len;j++){
if(!r->ch[str[j]-'A'])r->ch[str[j]-'A']=newNode();
r=r->ch[str[j]-'A'];
}
r->end=1;
}
for(i=0;i<26;i++)
if(ROOT->ch[i]){
ROOT->ch[i]->fail=ROOT;
dui.push(ROOT->ch[i]);
}
while(!dui.empty()){
Node *r=dui.front();dui.pop();
for(i=0;i<26;i++)
if(r->ch[i]){
Node *l = r->fail;
dui.push(r->ch[i]);
for(;l!=ROOT&&!l->ch[i];l=l->fail);
r->ch[i]->fail=l->ch[i]?l->ch[i]:ROOT;
}
}
for(i=0;i<26;i++)
if(ROOT->ch[i]){
ROOT->next[i]=ROOT->ch[i];
dui.push(ROOT->ch[i]);
}else ROOT->next[i]=ROOT;

while(!dui.empty()){
Node *r = dui.front();dui.pop();
for(i=0;i<26;i++)
if(r->ch[i]){
r->next[i]=r->ch[i];
dui.push(r->ch[i]);
}else r->next[i]=r->fail->next[i];
}
int ans=pow(26,m),l;
l=dp(0,ROOT);
printf("%d",(ans-l+MOD)%MOD);
return 0;
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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