BZOJ1030 [JSOI2007]文本生成器 AC自动机 动态规划

时间：2023-03-08 23:56:23
BZOJ1030 [JSOI2007]文本生成器 AC自动机 动态规划

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

题目传送门 - BZOJ1030

题意概括

　　给出n个模式串，问长度为m的串中有多少个至少含有这n个模式串中的任意一个。

　　注意，所有的串仅由A~Z 26个大写字母构成。

题解

　　AC自动机好题。

　　先构建一个AC自动机。

　　然后在AC自动机上面跑dp。

　　建议开滚动数组。

　　dp[i][j]表示长度为i，在AC自动机上面走到了j的方案数。

　　每次把所有走到模式串尾的全动统计到答案并清零。

代码

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <cstdio>

#include <cmath>

using namespace std;

const int N=+,L=+,Trie_Size=N*L;

const int mod=;

struct Trie{

    int fail,e;

    int next[];

    void set(){

        fail=e=;

        memset(next,,sizeof next);

    }

}tree[Trie_Size];

int cnt;

void AC_init(){

    cnt=;

    tree[].set(),tree[].set();

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

        tree[].next[i]=;

}

void add(char ch[]){

    int len=strlen(ch),rt=,t;

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

        t=ch[i]-'A';

        if (!tree[rt].next[t]){

            tree[++cnt].set();

            tree[rt].next[t]=cnt;

        }

        rt=tree[rt].next[t];

    }

    tree[rt].e=;

}

void build_AC(){

    int q[Trie_Size],head=,tail=,rt,son,k;

    q[++tail]=,tree[].fail=;

    while (head<tail){

        rt=q[++head];

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

            son=tree[rt].next[i];

            if (!son){

                tree[rt].next[i]=tree[tree[rt].fail].next[i];

                continue;

            }

            k=tree[rt].fail;

            while (!tree[k].next[i])

                k=tree[k].fail;

            tree[son].fail=tree[k].next[i];

            tree[son].e|=tree[tree[k].next[i]].e;

            q[++tail]=son;

        }

    }

}

int n,m,dp[Trie_Size],pre[Trie_Size],Pow[L];

char str[L];

int main(){

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

    AC_init();

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

        scanf("%s",&str);

        add(str);

    }

    build_AC();

    Pow[]=;

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

        Pow[i]=Pow[i-]*%mod;

    memset(dp,,sizeof dp);

    memset(pre,,sizeof pre);

    dp[]=;

    int ans=;

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

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

            pre[j]=dp[j];

        memset(dp,,sizeof dp);

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

            if (pre[j]>)

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

                    dp[tree[j].next[k]]=(dp[tree[j].next[k]]+pre[j])%mod;

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

            if (tree[j].e){

                ans=(ans+dp[j]*Pow[m-i])%mod;

                dp[j]=;

            }

    }

    printf("%d",ans);

    return ;

}

相关文章