程序员人生网站导航

uva 11468 - Substring(AC自动机+概率)

栏目：互联网时间：2014-09-08 01:35:11

题目链接：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
", kcas, getProb(0, n));
    }
    return 0;
}

------分隔线----------------------------

上一篇 Symfony2 Doctrine 数据库查询方法总结

下一篇 Mozilla与三星之子――Servo特性解读

------分隔线----------------------------