BZOJ1030 [JSOI2007]文本生成器（AC自动机）

时间：2023-03-09 19:50:21
BZOJ1030 [JSOI2007]文本生成器（AC自动机）

做到了AC自动机的题目，复习了一下AC自动机，学习了黄学长代码，这个题呢，我们可以模拟在AC自动机上的操作，dp数组f[i][j]表示前i个字符，我们在AC自动机上处在j号节点的方案数。

我们可以计算不符合条件的方案数，转移的时候不在有标记的节点转移就行了。—— by VANE

#include<bits/stdc++.h>

using namespace std;

const int N=;

struct node

{

    int son[],danger,fail;

}ch[N];

int n,m,f[][],tot=;

const int mod=;

char t[];

void insert(char s[])

{

    int now=,len=strlen(s);

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

    {

        int w=s[i]-'A';

        if(ch[now].son[w]) now=ch[now].son[w];

        else now=ch[now].son[w]=++tot;

    }

    ch[now].danger=;

}

void acmach()

{

    queue<int> q;

    q.push();ch[].fail=;

    while(!q.empty())

    {

        int u=q.front();q.pop();

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

        {

            if(!ch[u].son[i]) continue;

            int v=ch[u].fail;

            while(!ch[v].son[i]) v=ch[v].fail;

            ch[ch[u].son[i]].fail=ch[v].son[i];

            if(ch[ch[v].son[i]].danger) ch[ch[u].son[i]].danger=;

            q.push(ch[u].son[i]);

        }

    }

}

void dp(int x)

{

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

    {

        if(ch[i].danger||!f[x-][i]) continue;

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

        {

            int k=i;

            while(!ch[k].son[j]) k=ch[k].fail;

            f[x][ch[k].son[j]]=(f[x][ch[k].son[j]]+f[x-][i])%mod;

        }

    }

}

int main()

{

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

    for(int i=;i<;++i) ch[].son[i]=;

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

    {

        scanf("%s",t);

        insert(t);

    }

    acmach();

    f[][]=;

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

    int sum=;

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

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

    if(!ch[i].danger) sum=(sum-f[m][i]+mod)%mod;

    cout<<sum;

}

相关文章