P4052 [JSOI2007]文本生成器

P4052 [JSOI2007]文本生成器

AC自动机+dp

优秀题解传送门

设f[ i ][ j ]表示串的长度为 i ，当前在 j 点时不可识别的串的方案数

最后用总方案数减去不可识别方案数就是答案了

因为题解写的很好所以我就只在代码中加点注释了（逃

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int mod=;

struct data{

    int nxt[],fail,end;

}a[];

int n,m,cnt,ans=,f[][];

char q[];

inline void Trie_build(){

    scanf("%s",q);

    int u=,len=strlen(q);

    for(int i=;i<len;++i){

        int p=q[i]-'A';

        if(!a[u].nxt[p]) a[u].nxt[p]=++cnt;

        u=a[u].nxt[p];

    }++a[u].end;

}

inline void AC_build(){

    queue <int> h;

    for(int i=;i<;++i) if(a[].nxt[i]) h.push(a[].nxt[i]);

    while(!h.empty()){

        int x=h.front(); h.pop();

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

            int &to=a[x].nxt[i];

            if(to){

                a[to].fail=a[a[x].fail].nxt[i];

                a[to].end|=a[a[to].fail].end; //如果该串的后缀是可识别的那么这个串也一定是可识别的

                h.push(to);

            }else to=a[a[x].fail].nxt[i];

        }

    }

}

int main(){

    scanf("%d%d",&n,&m);

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

    AC_build();

    f[][]=;

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

        for(int j=;j<=cnt;++j)

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

                if(!a[a[j].nxt[k]].end) //不可识别

                    f[i][a[j].nxt[k]]=(f[i][a[j].nxt[k]]+f[i-][j])%mod;

    for(int i=;i<=m;++i) ans=ans*%mod;

    for(int i=;i<=cnt;++i) ans=(ans-f[m][i]+mod)%mod; //总方案数-不可识别方案数

    printf("%d",ans);

    return ;

}