给出一些字符和各自对应的选择概率，随机选择L次后得到一个长度为L的随机字符串S。

给出K个模板串，计算S不包含任何一个模板串的概率

 

dp[i][j]表示现在在AC自动机的i号点，还需要走j步的概率

dp[i][j]=Σdp[k][j-1] ，k不是单词节点

 

注意：

1、模板串可能是模板串的后缀，所以这题要用AC自动机，而不是Trie

2、在构造失配指针时，如果边不存在，要补上，边（不是失配指针）指向父节点的失配指针的子节点

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;char s[21];int len,tot,trie[21*21][63];bool mark[21*21],v[21*21][21*21];double p[21*21],dp[21*21][21*21];char ch[21*21];int f[21*21];int n;queue
         
          q;int get(char c){    if(c>='0'&&c<='9') return c-'0';    if(c>='a'&&c<='z') return c-'a'+10;    return c-'A'+36;}void insert(){    len=strlen(s);    int root=1,id;    for(int i=0;i
          
           >ch[i]; scanf("%lf",&p[i]); } int L; scanf("%d",&L); printf("Case #%d: %.6lf\n",t,dpp(1,L)); }}
          
         
        
       
      
     

 

 

另一种构造失配指针的写法

2个地方不一样

1、AC自动机从0开始，上面0作为虚拟节点

2、0不能直接入队，枚举0节点的孩子，让孩子入队

    因为0的失配指针是0

f[trie[now][i]]=trie[j][i]=trie[0][i]=本节点  导致失配指针指向自己 上面让1入队，1的失配指针是0

   

void getfail(){    memset(f,0,sizeof(f));    for(int i=0;i<63;i++)       if(trie[0][i]) q.push(trie[0][i]);    int now,j;    while(!q.empty())    {        now=q.front(); q.pop();         for(int i=0;i<63;i++)        {            if(!trie[now][i])             {                trie[now][i]=trie[f[now]][i];                continue;            }            q.push(trie[now][i]);            j=f[now];            //while(!trie[j][i]) j=f[j];            f[trie[now][i]]=trie[j][i];            if(mark[trie[j][i]]) mark[trie[now][i]]=true;        }    }}