题目链接:uva 11468 - Substring
题目大意:给出一些字符和各自字符对应的选择概率,随机选择L次后得到一个长度为L的字符串,要求该字符串不包含任意一个子串的概率。
解题思路:构造AC自动机之后,每随机生成一个字母,等于是在AC自动机上走一步,所有子串的结束位置的节点标记为禁止通行,然后问题转换成记忆搜索处理。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int sigma_size = 62;
const int maxn = 405;;
double pi[sigma_size], dp[maxn][105];
int vis[maxn][105];
int sz;
int ac[maxn][sigma_size];
int fail[maxn], last[maxn];
inline int idx (char ch) {
if (ch >= '0' && ch <= '9')
return ch - '0';
if (ch >= 'a' && ch <= 'z')
return ch - 'a' + 10;
if (ch >= 'A' && ch <= 'Z')
return ch - 'A' + 36;
return 0;
}
void ahoc_insert (char *s) {
int u = 0, n = strlen(s);
for (int i = 0; i < n; i++) {
int v = idx(s[i]);
if (ac[u][v] == 0) {
last[sz] = 0;
memset(ac[sz], 0, sizeof(ac[sz]));
ac[u][v] = sz++;
}
u = ac[u][v];
}
last[u] = 1;
}
void ahoc_fail () {
queue<int> que;
for (int i = 0; i < sigma_size; i++) {
int u = ac[0][i];
if (u) {
fail[u] = 0;
que.push(u);
}
}
while (!que.empty()) {
int r = que.front();
que.pop();
for (int i = 0; i < sigma_size; i++) {
int u = ac[r][i];
if (u == 0) {
ac[r][i] = ac[fail[r]][i];
continue;
}
que.push(u);
int v = fail[r];
while (v && !ac[v][i])
v = fail[v];
fail[u] = ac[v][i];
last[u] |= last[fail[u]];
}
}
}
void init () {
int n, x;
char str[sigma_size];
memset(pi, 0, sizeof(pi));
memset(vis, 0, sizeof(vis));
sz = 1;
fail[0] = last[0] = 0;
memset(ac[0], 0, sizeof(ac[0]));
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%s", str);
ahoc_insert(str);
}
ahoc_fail();
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%s", str);
scanf("%lf", &pi[idx(str[0])]);
}
}
double getProb (int u, int dep) {
if (dep == 0)
return 1.0;
if (vis[u][dep])
return dp[u][dep];
vis[u][dep] = 1;
double& ans = dp[u][dep];
ans = 0;
for (int i = 0; i < sigma_size; i++) {
if (last[ac[u][i]] == 0)
ans += pi[i] * getProb(ac[u][i], dep - 1);
}
return ans;
}
int main () {
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
init();
int n;
scanf("%d", &n);
printf("Case #%d: %.6lf\n", kcas, getProb(0, n));
}
return 0;
}
分享到:
相关推荐
17.7.7 fn:substring 543 17.7.8 fn:substringbefore 544 17.7.9 fn:substringafter 544 17.7.10 fn:split 545 17.7.11 fn:join 546 17.7.12 fn:tolowercase 547 17.7.13 fn:touppercase 547 17.7.14 fn:trim...
./0003-longest-substring-without-repeating-characters.cpp ./0004-median-of-two-sorted-arrays.cpp ./0005-longest-palindromic-substring.cpp ./0006-zigzag-conversion.cpp ./0007-reverse-integer.cpp ./0008...
String date = file_unique.substring(0,7); path = date+"/"+file_unique; System.out.println("--下载路径--:"+path); System.out.println("----"); System.out.println("--------"); //sPath = HttpRequest...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
前几篇文章给大家介绍了MySQL中的替换函数(Replace)、切分函数(SubString),今天我们一起来看看MySQL专业拼接“字符串”的函数:concat。...+----+---------------+--------------+-------+ | id |
zsh-history-substring-search 这是的历史记录搜索功能的无尘室实现,您可以在其中键入历史记录中任何命令的任何部分,然后按选定的键(例如UP和DOWN箭头)来循环进行匹配。 要求 4.3或更高版本 安装 使用软件包...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. ...
Substring Without Repeating Characters 无重复字符的最长子串 string 4 LMedian of Two Sorted Arrays 两个排序数组的中位数 ary,binary search,dive and conquer 5 Longest Palindromic Substring 最长回文子串 ...
练习-找到最大的子字符串 已发布的练习与BOOTCAMP培训-NodeJS Developer-JavaScript搜索和替换简介有关( )。 挑战说明: 在两个报告的字符串之间找到最大的公共子字符串。 子字符串可以是字符串的任何部分,包括...
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 1000。 Example 1: Input: "babad" Output: "bab" Note: "aba" is also ...substri
练习-尴尬面试(删除重复的角色) 已发布的练习与BOOTCAMP培训-NodeJS Developer-JavaScript故障排除有关。 ( )挑战说明: 营养学家朱莉安娜·阿尔坎特拉(Juliana Alcantra)是她所在领域的杰出专家。...
html-substring 允许对html内容进行子字符串化JavaScript代码。 只有实际的文本内容(没有标签,参数等)才计入字符数。 用法 /** * Returns html that is stripped to certain character length * @param { ...
$ npm install -- save surround - substring 用法 var surroundSubstring = require ( "surround-substring" ) ; var newString = surroundSubstring ( "*" , "really" , "I really like you!" ) console . log ( ...
import java.util.ArrayList; import java.util.List; public class Participle ... String str = exampleWord.substring(i, i + PARTICIPLE_LENGTH); result.add(str); } System.out.println(result); } }
Longest-Palindromic-Substring(最长回文子串) 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 Sample 1 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 Sample 2 输入...
String year = id.substring(6,10); String month = id.substring(10,12); String day = id.substring(12,14); System.out.println("您的生日是:" + year + "-" + month + "-" + day); } ...
/** * 匹配的例子: * (GC_F_BA_ACD_FDALFD_I_FALDJF) * (GC_F_BA_ACD_FDALFD) * (GC_F_BA_ACD)等 ... String res = group.substring(1, group.length() - 1); System.out.println(group + ":" + res); } }
package string_学习;... src = src.substring(pos + find.length());// 截取位置 3 h += (pos + find.length());// h为截取的字符数 0+3 } } else { System.out.println("不包含该字串"); }
AC自动机 Aho-Corasick-Automation 单源最短路径(SPFA) Bellman-Ford(Queue-Optimised) 单源最短路径(Bellman-Ford) Bellman-Ford 使用Edmonds-Karp进行二分图匹配 Bigrpah-Matching(Edmonds-Karp) 普通的...
substring截取字符串 substring截取字符串 substring截取字符串 substring截取字符串 substring截取字符串 substring截取字符串 substring截取字符串 substring截取字符串 substring截取字符串 substring截取字符串 ...