UVA 11468 Substring （AC自动机）

用把失配边也加到正常边以后AC自动机，状态是长度递减的DAG，每次选一个不会匹配字符的转移。

dp[u][L]表示当前在tire树上u结点长度还剩L时候不匹配的概率，根据全概率公式跑记忆化搜索。

#include<bits/stdc++.h>

using namespace std;

typedef double ld;

const int maxnds = *, sigma_size = ;

int nds;

int ch[maxnds][sigma_size];

double p[sigma_size];

int f[maxnds];

int id[];

bool val[maxnds];

int N;

void getF()

{

    queue<int> q;

    f[] = ;

    for(int c = ; c < sigma_size; c++){

        int u = ch[][c];

        if(u) { q.push(u); f[u] = ; }

    }

    while(q.size()){

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

        for(int c = ; c < sigma_size; c++){

            int u = ch[r][c];

            if(!u) {

                ch[r][c] = ch[f[r]][c]; continue;

            }

            q.push(u);

            int v = f[r];

            while(v && !ch[v][c]) v = f[v];

            f[u] = ch[v][c];

            val[u] |= val[f[u]];

        }

    }

}

void add(char *s)

{

    int n = strlen(s), u = ;

    for(int i = ; i < n; i++){

        int c = id[s[i]];

        if(!ch[u][c]){

            memset(ch[nds],,sizeof(ch[nds]));

            val[nds] = false;

            ch[u][c] = nds++;

        }

        u = ch[u][c];

    }

    val[u] = true;

}

const int maxL = ;

ld dp[maxnds][maxL];

bool vis[maxnds][maxL];

bool exist[sigma_size];

ld dfs(int u,int L)

{

    if(!L) return ;

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

    vis[u][L] = true;

    ld &ret = dp[u][L];

    ret = ;

    for(int i = ; i < sigma_size; i++)if(exist[i]){

        if(!val[ch[u][i]]) ret += p[i]*dfs(ch[u][i],L-);

    }

    return ret;

}

int id_cnt;

void init()

{

    memset(ch[],,sizeof(ch[]));

    nds = ;

    val[] = false;

    memset(exist,,sizeof(exist));

}

#define cerid ,cout<<id[i]<<endl

#define cer(x) cout<<x<<endl;

const int maxn = ;

char temp[maxn];

int main()

{

    //freopen("in.txt","r",stdin);

    for(int i = ''; i <= ''; i++) id[i] = i-'' ;

    for(int i = 'A'; i <= 'Z'; i++) id[i] = i-'A'+ ;

    for(int i = 'a'; i <= 'z'; i++) id[i] = i-'a'+ ;

    int T;cin>>T;

    int kas = ;

    while(T--){

        init();

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

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

            scanf("%s",temp);

            add(temp);

        }

        scanf("%d",&N);

        for(int i = ; i < N; i++){

            scanf("%s",temp);

            scanf("%lf",p+id[*temp]);

            exist[id[*temp]] = true;

        }

        getF();

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

        memset(vis,,sizeof(vis));

        printf("Case #%d: %lf\n",++kas,dfs(,L));

    }

    return ;

}