poj1625Censored!(AC自动机+dp）

第一次做这种题目，参考了下题解，相当于把树扯直了做DP，估计这一类题都是这个套路吧。

状态方程dp[i][next] = dp[i][next]+dp[i][j] ;dp[i][j]表示长度为i的第J个结点的时候满足题意的num，next为当前j点所能走到的下一个合法的结点。

需要用高精度，看到一些规范的高精度写法，觉得不错，有空整理下来。

不知道是不是我理解错了，按理说字符串病毒长度不应超过10.。但开到55依旧RE，开550AC。。。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 110

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 const int child_num = ;

 const int BASE = ;

 const int DIG = ;

 char s[N*],vir[];

 int id[];

 struct bignum

 {

      int a[],len;

      bignum()

      {

          memset(a,,sizeof(a));

          len = ;

      }

      bignum(int v)

      {

          memset(a,,sizeof(a));

          len = ;

          do

          {

              a[len++] = v%BASE;

              v/=BASE;

          }while(v);

      }

      /*bignum(const char s[])

      {

          memset(a,0,sizeof(a));

          int k = strlen(s);

          len = k/DIG;

          if(k%DIG) len++;

          int cnt = 0;

          for(int i = k-1;  i >= 0 ; i-=DIG)

          {

              int t = 0;

              int kk = i-DIG+1;

              if(kk<0) kk =0;

              for(int j = kk ; j <= i ; j++)

              t = t*10+s[j]-'0';

              a[cnt++] = t;

          }

      }*/

      bignum operator + (const bignum &b)const

      {

          bignum res;

          res.len = max(len,b.len);

          int i;

          for(i =  ; i < res.len ;i ++)

          res.a[i] = ;

          for(i =  ; i < res.len ; i++)

          {

              res.a[i] += ((i<len)?a[i]:)+((i<b.len)?b.a[i]:);

              res.a[i+] += res.a[i]/BASE;

              res.a[i] = res.a[i]%BASE;

          }

          if(res.a[res.len]>) res.len++;

          return res;

      }

      void output()

      {

          printf("%d",a[len-]);

          for(int i = len- ; i >= ; i--)

          printf("%04d",a[i]);

          printf("\n");

      }

 }dp[][];

 class AC

 {

     private:

     int ch[N][child_num];

     int Q[N];

     int val[N];

     int fail[N];

     //int id[N];

     int sz;

     public :

     void init()

     {

         fail[] = ;

         //for(int i = 0 ;i < child_num-32 ; i++)

         //id[i+32] = i;

     }

     void reset()

     {

         memset(val,,sizeof(val));

         memset(fail,,sizeof(fail));

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

         sz = ;

     }

     void insert(char *a,int key)

     {

         int k = strlen(a),p = ;

         for(int i =  ; i < k ;i++)

         {

             int d = id[a[i]];

             if(ch[p][d]==)

             {

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

                 ch[p][d] = sz++;

             }

             p = ch[p][d];

         }

         val[p] = key;

     }

     void construct(int n)

     {

         int i,head=,tail = ;

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

         {

             if(ch[][i])

             {

                 Q[tail++] = ch[][i];

                 fail[ch[][i]] = ;

             }

         }

         while(head!=tail)

         {

             int u = Q[head++];

             val[u]|=val[fail[u]];

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

             {

                 if(ch[u][i])

                 {

                     Q[tail++] = ch[u][i];

                     fail[ch[u][i]] = ch[fail[u]][i];

                 }

                 else ch[u][i] = ch[fail[u]][i];

             }

         }

     }

     void work(int m,int n)

     {

         int i,j,g;

         for(i = ; i <= m ;i++)

             for(j =  ;j <= sz; j++)

             dp[i][j] = bignum();

         dp[][] = bignum();

         for(i =  ; i < m ;i++)

         {

             for(j =  ; j < sz ;j++)

             for(g =  ; g < n ; g++)

             if(!val[ch[j][g]])

             {

                 dp[i+][ch[j][g]]=dp[i+][ch[j][g]]+dp[i][j];

             }

         }

         bignum ans = bignum();

         for(j =  ;j < sz ; j++)

         ans=ans+dp[m][j];

         ans.output();

     }

 }ac;

 int main()

 {

     int n,m,i,p;

     ac.init();

     while(cin>>n>>m>>p)

     {

         cin>>s;

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

         id[s[i]] = i;

         ac.reset();

         for(i = ;i <= p; i++)

         {

             scanf("%s",vir);

             ac.insert(vir,);

         }

         ac.construct(n);

         ac.work(m,n);

     }

     return ;

 }

巴特西

poj1625Censored!(AC自动机+dp）

最新文章

热门文章