UVA 11468 Substring (记忆化搜索 + AC自动鸡)

题意：给你K个模式串，然后，再给你 n 个字符，和它们出现的概率 p[ i ]，模式串肯定由给定的字符组成。

　　　且所有字符，要么是数字，要么是大小写字母。问你生成一个长度为L的串，不包含任何模式串的概率是多少。

解：记忆化搜索 + AC自动机。对模式串建一个AC自动机，不需要last[ ] 和 val[ ]，只需要一个 metch[ ]。

　　维护一下这个点是否是某个模式串的最后一个字符节点，若是，则这个点不能走。

　　然后，剩下的就是从根节点，随便走 L 步，记得要记忆化，否则超时。

　　记得数组开足够大，否则 wa 一下午。

#include <bits/stdc++.h>

#define LL long long

#define rep(i, j, k) for(int i = j; i <= k; i++)

#define dep(i, j, k) for(int i = k; i >= j; i--)

#define INF 0x3f3f3f3f

#define inf 0x3f3f3f3f3f3f3f3f

#define mem(i, j) memset(i, j, sizeof(i))

#define pb push_back

using namespace std;

const int N =  *  + , M = ;

char op[];

double tmp;

struct Trie {

    int a[N][M], tot, metch[N], Fail[N], vis[N][M], n;

    double p[N], dp[N][M];

    char ch[M];

    void init() {

        mem(a[], ); tot = ; metch[] = ; mem(dp, ); mem(p, ); mem(vis, );

    }

    int get(char Q) {

        if(Q >= '' && Q <= '') return Q - '' + ;

        if(Q >= 'A' && Q <= 'Z') return Q - 'A' + ;

        return Q - 'a' + ;

    }

    void join(char s[]) {

        int now = ; int len = strlen(s);

        rep(i, , len - ) {

            int id = get(s[i]);

            if(!a[now][id]) {

                mem(a[tot], ); metch[tot] = ;

                a[now][id] = tot++;

            }

            now = a[now][id];

        }

        metch[now] = ;

    }

    void getFail() {

        queue<int> Q; while(!Q.empty()) Q.pop();

        rep(i, , M - ) {

            if(a[][i]) {

                Q.push(a[][i]); Fail[a[][i]] = ;

            }

        }

        while(!Q.empty()) {

            int now = Q.front(); Q.pop();

            rep(i, , M - ) {

                int u = a[now][i];

                if(u == ) a[now][i] = a[Fail[now]][i];

                else {

                    Q.push(u);

                    Fail[u] = a[Fail[now]][i];

                    metch[u] |= metch[Fail[u]];

                }

            }

        }

    }

    double dfs(int now, int L) {

        if(!L) return 1.0;

        if(vis[now][L]) return dp[now][L];

        vis[now][L] = ;

        double &ans = dp[now][L];

        ans = 0.0;

        rep(i, , M - ) { /// 枚举所有可能字符

            if(!metch[a[now][i]]) { /// 这个节点可以走

                ans += p[i] * dfs(a[now][i], L - );

            }

        }

        return ans;

    }

    void scan() {

        scanf("%d", &n);

        rep(i, , n) {

            scanf("%s %lf", op, &tmp);

            int id = get(op[]);

            p[id] = tmp;

        }

    }

    void print(int cas) {

        int L; scanf("%d", &L);

        printf("Case #%d: ", cas);

        printf("%.6f\n", dfs(, L));

    }

};

Trie AC;

char b[];

int main() {

    int _; scanf("%d", &_); int cas = ;

    while(_--) {

        AC.init();

        int k; scanf("%d", &k);

        rep(i, , k) {

            scanf("%s", b); AC.join(b);

        }

        AC.getFail();

        AC.scan();

        AC.print(++cas);

    }

    return ;

}

巴特西

UVA 11468 Substring (记忆化搜索 + AC自动鸡)

最新文章

热门文章