POJ 1625 Censored! [AC自动机 高精度]

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=105,M=55,L=30,B=1e4;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
    return x*f;
}
int n,m,p,mp[300];
char s[N];
struct node{
    int ch[55],fail,val;
}t[N];
int sz;
void ins(char s[]){
    int u=0,n=strlen(s+1);
    for(int i=1;i<=n;i++){
        int c=mp[s[i]];
        if(!t[u].ch[c]) t[u].ch[c]=++sz;
        u=t[u].ch[c];
    }
    t[u].val=1;
}
int q[N],head,tail;
void getAC(){
    head=tail=1;
    for(int i=1;i<=mp[0];i++) if(t[0].ch[i]) q[tail++]=t[0].ch[i];
    while(head!=tail){
        int u=q[head++];
        t[u].val|=t[t[u].fail].val;
        for(int i=1;i<=mp[0];i++){
            int &v=t[u].ch[i];
            if(!v) v=t[t[u].fail].ch[i];
            else{
                t[v].fail=t[t[u].fail].ch[i];
                q[tail++]=v;
            }
        }
    }
}

struct big{
    int size,d[L];
    big():size(1){memset(d,0,sizeof(d));}
    bool has(){return size>1||(size==1&&d[1]!=0);}
};
big operator +(big a,big b){
    int g=0,i;
    for(i=1;;i++){
        if(g==0&&i>a.size&&i>b.size) break;
        int t=g;
        t+=i<=a.size?a.d[i]:0;
        t+=i<=b.size?b.d[i]:0;
        a.d[i]=t%B;
        g=t/B;
    }
    a.size=i-1;
    return a;
}
void print(big &a){
    printf("%d",a.d[a.size]);
    for(int i=a.size-1;i>=1;i--){
        if(a.d[i]<10) printf("000");
        else if(a.d[i]<100) printf("00");
        else if(a.d[i]<1000) printf("0");
        printf("%d",a.d[i]);
    }
    putchar(‘\n‘);
}

big f[M][N],ans;
void dp(){
    f[0][0].d[1]=1;
    for(int i=0;i<m;i++)
        for(int j=0;j<=sz;j++) if(!t[j].val&&f[i][j].has())
            for(int k=1;k<=mp[0];k++) if(!t[t[j].ch[k]].val)
                f[i+1][t[j].ch[k]]=f[i+1][t[j].ch[k]]+f[i][j];
    for(int i=0;i<=sz;i++) ans=ans+f[m][i];
    print(ans);
}
int main(){
    freopen("in","r",stdin);
    n=read();m=read();p=read();
    scanf("%s",s+1);
    for(int i=1;i<=n;i++) mp[s[i]]=i;mp[0]=n;
    for(int i=1;i<=p;i++) scanf("%s",s+1),ins(s);
    //for(int i=1;i<=n;i++) printf("mp %c %d\n",s[i],mp[s[i]]);
    getAC();
    dp();
}