UVA 11468 Ac自动机+dp - c++编程基础

TOP

UVA 11468 Ac自动机+dp

2015-07-20 17:22:37 来源: 作者: 【大中小】浏览:2次

题目意思：给出k个模式串，然后随机生成一个长度为L字符串，每个字符被选中的概率为pi 。问构造出来的字符串不包含任何模式串的概率。

分析：显然这是一个模式串的母串的匹配，显然需要先构建一个AC自动机。我们用dp[i][j] 表示当前正在构造第i个字符，fail指针在j节点上能构造成功的概率。那么我们可以顺着fail指针向后面的状态。注意只能扩展有效状态，也即不包含任何模式串的状态。也即

dp [i][j]->dp[i+1][ch[j][k] ]; ch[j][k] 表示如果选k字符的话的下一状态。

VIEW CODE

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                using namespace std; const int mmax=2100; struct AC_trie { double dp[110][mmax]; int ch[mmax][63]; int cnt[mmax],Fail[mmax],match[mmax]; int num,k,L,n; char patter[30]; double p[70]; int get_id(char c) { if('0'<=c && c<='9') return c-'0'; if('A'<=c && c<='Z') return c-'A'+10; if('a'<=c && c<='z') return c-'a'+36; return 0; } void init() { memset(ch,0,sizeof ch); memset(match,0,sizeof match); memset(cnt,0,sizeof cnt); cnt[0]=0; num=0; memset(p,0,sizeof p); memset(dp,0,sizeof dp); } void read(int n) { for(int i=0;i
               
                q; Fail[0]=0; for(int i=0;i<62;i++) { int u=ch[0][i]; if(u) { q.push(u); Fail[u]=0; } } while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0;i<62;i++) { int u=ch[x][i]; if(!u) { ch[x][i]=ch[Fail[x]][i]; continue; } q.push(u); int v=Fail[x]; while(v && !ch[v][i]) v=Fail[v]; Fail[u]=ch[v][i]; match[u] |=match[Fail[u]]; } } } void work() { init(); scanf("%d",&k); read(k); scanf("%d",&n); for(int i=0;i
                
                 >t; while(t--) { printf("Case #%d: ",++ca); Ac.work(); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：codeforecs--D. Tanya and Passwo..	下一篇：poj-3628 Silver Cow Party

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: