您當前位置：首頁 > 互聯(lián)網(wǎng) > uva 11468 - Substring(AC自動機+概率)

uva 11468 - Substring(AC自動機+概率)

來源：程序員人生發(fā)布時間：2014-09-08 01:35:11 閱讀次數(shù)：3807次

題目鏈接：uva 11468 - Substring

題目大意：給出一些字符和各自字符對應的選擇概率，隨機選擇L次后得到一個長度為L的字符串，要求該字符串不包含任意一個子串的概率。

解題思路：構造AC自動機之后，每隨機生成一個字母，等于是在AC自動機上走一步，所有子串的結束位置的節(jié)點標記為禁止通行，然后問題轉換成記憶搜索處理。

#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;
}

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生

------分隔線----------------------------

上一篇 Symfony2 Doctrine 數(shù)據(jù)庫查詢方法總結

下一篇 Mozilla與三星之子――Servo特性解讀

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關注

欄目熱點

多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

uva 11468 - Substring(AC自動機+概率)