Substring UVA - 11468 AC自动机+概率DP-白红宇

Substring UVA - 11468 AC自动机+概率DP

阅读量：5030 次

发布时间：2019-06-12

本文共 2875 字，大约阅读时间需要 9 分钟。

题意：

给出一些字符和各自对应的选择概率，随机选择L次后得到一个长度为L的随机字符串S。

给出K个模板串，计算S不包含任何一个模板串的概率

dp【i】【j】表示走到AC自动机 i 这个节点还需要走 j 步的概率。

表示不会概率DP ，看网上题解写的。

通过记忆化搜索去写。

注意一点字符有大小字母和数字

1 #include 
      
         2 #include 
         3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 #include 
                  
                    14 15 #define pi acos(-1.0) 16 #define eps 1e-9 17 #define fi first 18 #define se second 19 #define rtl rt<<1 20 #define rtr rt<<1|1 21 #define bug printf("******\n") 22 #define mem(a, b) memset(a,b,sizeof(a)) 23 #define name2str(x) #x 24 #define fuck(x) cout<<#x" = "<
                   
                    <
                    
                     = 'a' && ch <= 'z') return ch - 'a'; 58 if (ch >= 'A' && ch <= 'Z') return ch - 'A' + 26; 59 if (ch >= '0' && ch <= '9') return ch - '0' + 52; 60 } 61 62 struct Aho_Corasick { 63 int next[410][66], fail[410], End[410]; 64 int root, cnt; 65 66 int newnode() { 67 for (int i = 0; i < 66; i++) next[cnt][i] = -1; 68 End[cnt++] = 0; 69 return cnt - 1; 70 } 71 72 void init() { 73 cnt = 0; 74 root = newnode(); 75 } 76 77 void insert(char buf[]) { 78 int len = strlen(buf); 79 int now = root; 80 for (int i = 0; i < len; i++) { 81 if (next[now][get_num(buf[i])] == -1) next[now][get_num(buf[i])] = newnode(); 82 now = next[now][get_num(buf[i])]; 83 } 84 End[now] = 1; 85 } 86 87 void build() { 88 queue
                     
                       Q; 89 fail[root] = root; 90 for (int i = 0; i < 66; i++) 91 if (next[root][i] == -1) next[root][i] = root; 92 else { 93 fail[next[root][i]] = root; 94 Q.push(next[root][i]); 95 } 96 while (!Q.empty()) { 97 int now = Q.front(); 98 Q.pop(); 99 End[now] |= End[fail[now]];100 for (int i = 0; i < 66; i++)101 if (next[now][i] == -1) next[now][i] = next[fail[now]][i];102 else {103 fail[next[now][i]] = next[fail[now]][i];104 Q.push(next[now][i]);105 }106 }107 }108 109 double solve(int pos, int res) {110 if (!res) return 1.0;111 if (vis[pos][res]) return dp[pos][res];112 vis[pos][res] = 1;113 double &ret = dp[pos][res];114 ret = 0;115 for (int i = 0; i < m; ++i) {116 int idx = id[i];117 if (!End[next[pos][idx]]) ret += pro[i] * solve(next[pos][idx], res - 1);118 }119 return ret;120 }121 122 void debug() {123 for (int i = 0; i < cnt; i++) {124 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]);125 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]);126 printf("]\n");127 }128 }129 } ac;130 131 int main() {132 // FIN;133 int cas = 1;134 sfi(T);135 while (T--) {136 sfi(n);137 ac.init();138 for (int i = 0; i < n; ++i) {139 sfs(buf);140 ac.insert(buf);141 }142 ac.build();143 sfi(m);144 for (int i = 0; i < m; ++i) {145 scanf("%s%lf", buf, &pro[i]);146 id[i] = get_num(buf[0]);147 }148 sfi(L);149 mem(vis, 0);150 printf("Case #%d: %.6f\n", cas++, ac.solve(0, L));151 }152 return 0;153 }