程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> UVA 11468 Ac自動機+dp

UVA 11468 Ac自動機+dp

編輯：關於C++

題目意思：給出k個模式串，然後隨機生成一個長度為L字符串，每個字符被選中的概率為pi 。問構造出來的字符串不包含任何模式串的概率。

分析：顯然這是一個模式串的母串的匹配，顯然需要先構建一個AC自動機。我們用dp[i][j] 表示當前正在構造第i個字符，fail指針在j節點上能構造成功的概率。那麼我們可以順著fail指針向後面的狀態。注意只能擴展有效狀態，也即不包含任何模式串的狀態。也即

dp [i][j]->dp[i+1][ch[j][k] ]; ch[j][k] 表示如果選k字符的話的下一狀態。

VIEW CODE

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int mmax=2100;


struct AC_trie
{
    double dp[110][mmax];
    int ch[mmax][63];
    int cnt[mmax],Fail[mmax],match[mmax];
    int num,k,L,n;
    char patter[30];
    double p[70];
    int get_id(char c)
    {
        if('0'<=c && c<='9')
            return c-'0';
        if('A'<=c && c<='Z')
            return c-'A'+10;
        if('a'<=c && c<='z')
            return c-'a'+36;
        return 0;
    }
    void init()
    {
        memset(ch,0,sizeof ch);
        memset(match,0,sizeof match);
        memset(cnt,0,sizeof cnt);
        cnt[0]=0;
        num=0;
        memset(p,0,sizeof p);
        memset(dp,0,sizeof dp);
    }

    void read(int n)
    {
        for(int i=0;iq;
        Fail[0]=0;
        for(int i=0;i<62;i++)
        {
            int u=ch[0][i];
            if(u)
            {
                q.push(u);
                Fail[u]=0;
            }
        }
        while(!q.empty())
        {
            int x=q.front();
            q.pop();
            for(int i=0;i<62;i++)
            {
                int u=ch[x][i];
                if(!u)
                {
                    ch[x][i]=ch[Fail[x]][i];
                    continue;
                }
                q.push(u);
                int v=Fail[x];
                while(v && !ch[v][i]) v=Fail[v];
                Fail[u]=ch[v][i];
                match[u] |=match[Fail[u]];
            }
        }
    }
    void work()
    {
        init();
        scanf("%d",&k);
        read(k);
        scanf("%d",&n);
        for(int i=0;i>t;
    while(t--)
    {
        printf("Case #%d: ",++ca);
        Ac.work();
    }
    return 0;
}