AC自动机+DP+大数poj1625

2 3 1
ab
bb

5

dp[i][j]表示第i步在第j个节点的方法数。flag[k]=0表示不是非法节点,son是k的儿子节点的集合。

　　dp[i][j]=sum(dp[i-1][k]*mat[k][j]&&val[ch[k][j]]==0);

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=110;
int SIGMA_SIZE;
int n,m,p;
char P[60],s[60];
map<char,int> mp;

struct Matrix
{
    int mat[maxn][maxn];
    Matrix(){memset(mat,sizeof(mat));}

};
struct AC
{
    int ch[maxn][256],val[maxn];
    int fail[maxn],last[maxn];
    int sz;
    void clear(){memset(ch[0],sizeof(ch[0]));sz=1;}
    int idx(char x){return mp[x];}
    void insert(char *s)
    {
        int n=strlen(s);
        int u=0;
        for(int i=0;i<n;i++)
        {
            int c=idx(s[i]);
            if(!ch[u][c])
            {
                memset(ch[sz],sizeof(ch[sz]));
                val[sz]=0;
                ch[u][c]=sz++;
            }
            u=ch[u][c];
        }
        val[u]=1;
    }
    void getfail()
    {
        queue<int> q;
        fail[0]=0;
        int u=0;
        for(int i=0;i<SIGMA_SIZE;i++)
        {
            u=ch[0][i];
            if(u){fail[u]=last[u]=0;q.push(u);}
        }
        while(!q.empty())
        {
            int r=q.front();q.pop();
            if(val[fail[r]])val[r]=1;
            for(int c=0;c<SIGMA_SIZE;c++)
            {
                u=ch[r][c];
                if(!u){ch[r][c]=ch[fail[r]][c];continue;}
                q.push(u);
                int v=fail[r];
                while(v&&!ch[v][c])v=fail[v];
                fail[u]=ch[v][c];
                last[u]=val[fail[u]]?fail[u]:last[fail[u]];
            }
        }
    }
    Matrix getMatrix()
    {
        Matrix res;
        for(int i=0;i<sz;i++)
            for(int j=0;j<SIGMA_SIZE;j++)
                if(!val[ch[i][j]])res.mat[i][ch[i][j]]++;
        return res;
    }
}ac;
/*
 * 高精度，支持乘法和加法
 */
struct BigInt
{
    const static int mod = 10000;
    const static int DLEN = 4;
    int a[600],len;
    BigInt()
    {
        memset(a,sizeof(a));
        len = 1;
    }
    BigInt(int v)
    {
        memset(a,sizeof(a));
        len = 0;
        do
        {
            a[len++] = v%mod;
            v /= mod;
        }while(v);
    }
    BigInt(const char s[])
    {
        memset(a,sizeof(a));
        int L = strlen(s);
        len = L/DLEN;
        if(L%DLEN)len++;
        int index = 0;
        for(int i = L-1;i >= 0;i -= DLEN)
        {
            int t = 0;
            int k = i - DLEN + 1;
            if(k < 0)k = 0;
            for(int j = k;j <= i;j++)
                t = t*10 + s[j] - '0';
            a[index++] = t;
        }
    }
    BigInt operator +(const BigInt &b)const
    {
        BigInt res;
        res.len = max(len,b.len);
        for(int i = 0;i <= res.len;i++)
            res.a[i] = 0;
        for(int i = 0;i < res.len;i++)
        {
            res.a[i] += ((i < len)?a[i]:0)+((i < b.len)?b.a[i]:0);
            res.a[i+1] += res.a[i]/mod;
            res.a[i] %= mod;
        }
        if(res.a[res.len] > 0)res.len++;
        return res;
    }
    BigInt operator *(const BigInt &b)const
    {
        BigInt res;
        for(int i = 0; i < len;i++)
        {
            int up = 0;
            for(int j = 0;j < b.len;j++)
            {
                int temp = a[i]*b.a[j] + res.a[i+j] + up;
                res.a[i+j] = temp%mod;
                up = temp/mod;
            }
            if(up != 0)
                res.a[i + b.len] = up;
        }
        res.len = len + b.len;
        while(res.a[res.len - 1] == 0 &&res.len > 1)res.len--;
        return res;
    }
    void output()
    {
        printf("%d",a[len-1]);
        for(int i = len-2;i >=0 ;i--)
            printf("%04d",a[i]);
        printf("n");
    }
};
BigInt dp[2][maxn];
int main()
{
    while(scanf("%d%d%d",&n,&m,&p)!=EOF)
    {
        scanf("%s",P);
        ac.clear();
        mp.clear();
        for(int i=0;i<strlen(P);i++)
            mp[P[i]]=i;
        SIGMA_SIZE=n;
        for(int i=0;i<p;i++)
        {
            scanf("%s",s);
            ac.insert(s);
        }
        ac.getfail();
        Matrix A=ac.getMatrix();
        int now=0;
        dp[now][0]=1;
        for(int i=1;i<ac.sz;i++)dp[now][i]=0;
        for(int i=1;i<=m;i++)
        {
            now^=1;
            for(int j=0;j<ac.sz;j++)dp[now][j]=0;
            for(int j=0;j<ac.sz;j++)
                for(int k=0;k<ac.sz;k++)
                if(A.mat[j][k]>0)dp[now][k]=dp[now][k]+dp[now^1][j]*A.mat[j][k];
        }
        BigInt ans=0;
        for(int i=0;i<ac.sz;i++)
            ans=ans+dp[now][i];
        ans.output();
    }
    return 0;
}