題目大意：給你一些模板串和組成這些模板串的字符，從中隨機(jī)選L個(gè)字符，每個(gè)字符都有各自被選的概率p，保證p之和為1，問(wèn)抽到的串不包含模板串的概率

?

?

建一顆tire樹，不能走打了tag的標(biāo)記，走每條邊概率已知，求走到深度L的概率，dp[i][j]表示到第i個(gè)點(diǎn)還能走j步的概率，轉(zhuǎn)移即可

但這樣做存在問(wèn)題，可能某個(gè)短串是長(zhǎng)串的子串，但是上述做法無(wú)法判斷

可以建一顆tire樹，從某個(gè)節(jié)點(diǎn)不斷走fail，要求fail路徑上的點(diǎn)都沒有tag標(biāo)記

其實(shí)這就是last的功能，即最近一個(gè)t串相同的ag標(biāo)記的位置

?

莫名其妙空間開大了過(guò)不了，開小了過(guò)了，沒有memset? p數(shù)組過(guò)不了，memset了過(guò)了，是不是數(shù)據(jù)出的有問(wèn)題，串中含有給的字符里沒有的字符？

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <cmath> 9 #define min(a, b) ((a) < (b) ? (a) : (b)) 10 #define max(a, b) ((a) > (b) ? (a) : (b)) 11 #define abs(a) ((a) < 0 ? (-1 * (a)) : (a)) 12 inline void swap(int &a, int &b) 13 { 14 long long tmp = a;a = b;b = tmp; 15 } 16 inline void read(int &x) 17 { 18 x = 0;char ch = getchar(), c = ch; 19 while(ch < '0' || ch > '9') c = ch, ch = getchar(); 20 while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar(); 21 if(c == '-') x = -x; 22 } 23 24 const int INF = 0x3f3f3f3f; 25 26 int t, k, n, l, ch[2000][80], fail[2000], last[2000], cnt, tag[2000], ca, vis[2000][100]; 27 double p[800], dp[2000][100]; 28 char s[200][200], base[800]; 29 int check(char c) 30 { 31 if(c >= '0' && c <= '9') return c - '0' + 1; 32 if(c >= 'A' && c <= 'Z') return c - 'A' + 11; 33 return c - 'a' + 37; 34 } 35 void insert(int x) 36 { 37 int now = 0; 38 for(register int i = 1;s[x][i] != '\0';++ i) 39 { 40 int tmp = check(s[x][i]); 41 if(ch[now][tmp]) now = ch[now][tmp]; 42 else now = ch[now][tmp] = ++ cnt; 43 } 44 ++ tag[now]; 45 } 46 47 int q[1000], he, ta; 48 49 void build() 50 { 51 he = ta = 0; 52 for(register int i = 1;i <= 62;++ i) 53 if(ch[0][i]) q[ta ++] = ch[0][i], fail[ch[0][i]] = last[ch[0][i]] = 0; 54 while(he < ta) 55 { 56 int now = q[he ++]; 57 for(register int i = 1;i <= 62;++ i) 58 { 59 int u = ch[now][i]; 60 if(!u) 61 { 62 ch[now][i] = ch[fail[now]][i]; 63 continue; 64 } 65 q[ta ++] = u; 66 int v = fail[now]; 67 while(v && !ch[v][i]) v = fail[v]; 68 fail[u] = ch[v][i]; 69 last[u] = tag[fail[u]] ? fail[u] : last[fail[u]]; 70 } 71 } 72 } 73 74 double dfs(int x, int y) 75 { 76 if(!y) return 1; 77 if(vis[x][y]) return dp[x][y]; 78 vis[x][y] = 1; 79 dp[x][y] = 0; 80 for(register int i = 1;i <= 62;++ i) 81 if(!tag[ch[x][i]] && !last[ch[x][i]]) dp[x][y] += p[i] * dfs(ch[x][i], y - 1); 82 return dp[x][y]; 83 } 84 85 int main() 86 { 87 read(t); 88 for(ca = 1;t;-- t, ++ ca) 89 { 90 memset(ch, 0, sizeof(ch)), memset(tag, 0, sizeof(tag)), cnt = 0, memset(vis, 0, sizeof(vis));memset(p, 0, sizeof(p)); 91 read(k); 92 for(register int i = 1;i <= k;++ i) scanf("%s", s[i] + 1), insert(i); 93 read(n); 94 for(register int i = 1;i <= n;++ i) 95 scanf("%s", &base[i]), scanf("%lf", &p[check(base[i])]); 96 read(l); 97 build(); 98 printf("Case #%d: %.6lf\n", ca, dfs(0, l)); 99 } 100 return 0; 101 } UVA11468

?

轉(zhuǎn)載于:https://www.cnblogs.com/huibixiaoxing/p/8323441.html

總結(jié)

以上是生活随笔為你收集整理的UVA11468 Substring的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。