【UVA】11468-Substring（AC自己主动机）

AC自己主动机的题，须要注意的，建立失配边的时候，假设结点1失配边连到的那个结点2，那个结点2是一个单词的结尾，那么这个结点1也须要标记成1（由于能够看成，这个结点包括了这个单词），之后在Trie树上进行行走，每次走到下一个能够走的结点。

14378527

11468

Substring

Accepted

C++

0.585

2014-10-19 10:35:00

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn = 444;

const int max_size = 66;

const int maxd = 111;

int M,Case = 1;

int ch[max_size];

double P[max_size];

int index(int c){

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

    if(c >= 'a' && c <= 'z') return c - 'a' + 26;

    if(c >= '0' && c <= '9') return c - '0' + 52;

}

struct Trie{

    int next[maxn][max_size];

    int fail[maxn];

    int val[maxn];

    int vis[maxn][maxd];

    double dp[maxn][maxd];

    int sz,root;

    int newnode(){

        val[sz] = 0;

        memset(next[sz],-1,sizeof(next[sz]));

        sz ++;

        return sz - 1;

    }

    void init(){

       sz = 0;

       root = newnode();

       memset(vis,0,sizeof(vis));

       return;

    }

    void insert(char *str){

        int now = root;

        int L = strlen(str);

        for(int i = 0; i < L; i++){

            int e = index(str[i]);

            if(next[now][e] == -1)

               next[now][e] = newnode();

            now = next[now][e];

        }

        val[now] = 1;

        return;

    }

    void build(){

        queue<int>q;

        fail[root] = root;

        for(int i = 0; i < max_size ; i++)

            if(next[root][i] != -1){

                fail[next[root][i]] = root;

                q.push(next[root][i]);

            }

            else

                next[root][i] = root;

        while(!q.empty()){

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

            for(int i = 0; i < max_size ; i++){

                if(next[now][i] == -1)

                   next[now][i] = next[fail[now]][i];

                else{

                    q.push(next[now][i]);

                    fail[next[now][i]] = next[fail[now]][i];

                    val[next[now][i]] |= val[fail[next[now][i]]];

                }

            }

        }

        return;

    }

    double DP(int pos,int L){

        if(!L) return 1.0;

        if(vis[pos][L])

            return dp[pos][L];

        vis[pos][L] = 1;

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

        ans = 0.0;

        for(int i = 0; i < M; i++){

            int e = ch[i];

            if(!val[next[pos][e]])

                ans += P[i] * DP(next[pos][e],L - 1);

        }

        return ans;

    }

}ac;

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        ac.init();

        int K;

        scanf("%d",&K);

        for(int i = 0; i < K; i++){

            char str[maxn];

            scanf("%s",str);

            ac.insert(str);

        }

        ac.build();

        scanf("%d",&M);

        for(int i = 0; i < M; i++){

            char str[maxn];

            scanf("%s%lf",str,&P[i]);

            ch[i] = index(str[0]);

        }

        int L;

        scanf("%d",&L);

        double ans = ac.DP(0,L);

        printf("Case #%d: %.6f\n",Case++,ans);

    }

    return 0;

}