bzoj-1030（AC自动机+DP）

我不是女神ヾ 2021-12-12 01:47 344阅读 0赞

题意：给你n个匹配串，算出所有长度为m且至少包括1个匹配串的数量；

解题思路：首先根据题意，因为至少包括一个不好弄，根据容斥，我们可以把题目搞成求出所有长度为m不包括匹配串的字符串，然后减一下就是答案，求长度为m不包括有点像poj2778，但是因为状态太多，所有不能用矩阵，所以用dp解决，设dp【i】【j】表示当前第i个位置，且在trie图上j状态点的时候的数量。dp【i+1】【trie【j】【k】】+=dp【i】【j】；

代码：

#include<bits/stdc++.h>
    using namespace std;
    const int mod=10007;
    const int N=6050;
    int trie[N][26];
    int fail[N];
    int visit[N];
    int n,m,tot;
    int dp[110][N];
    char t[150];
    void build_trie(char *str)
    {
        int root=0;
        int len=strlen(str);
        for(int i=0;i<len;i++)
        {
            int id=str[i]-'A';
            if(!trie[root][id])
                trie[root][id]=++tot;
            root=trie[root][id];
        }
        visit[root]=1;
    }
    void build_fail()
    {
        queue<int>q;
        for(int i=0;i<26;i++)
            if(trie[0][i]!=0)
                q.push(trie[0][i]);
        while(!q.empty())
        {
            int now=q.front();q.pop();
            if(visit[fail[now]])
                visit[now]=1;
            for(int i=0;i<26;i++)
            {
                if(!trie[now][i])
                {
                    trie[now][i]=trie[fail[now]][i];
                    continue;
                }
                fail[trie[now][i]]=trie[fail[now]][i];
                q.push(trie[now][i]);
            }
        }
    }
    void init()
    {
        memset(fail,0,sizeof(fail));
        memset(trie,0,sizeof(trie));
        memset(visit,0,sizeof(visit));
        memset(dp,0,sizeof(dp));
        tot=0;
    }
    int solve()
    {
        dp[0][0]=1;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<=tot;j++)
            {
                if(visit[j])continue;
                for(int k=0;k<26;k++)
                {
                    if(visit[trie[j][k]])continue;
                    dp[i+1][trie[j][k]]=(dp[i+1][trie[j][k]]+dp[i][j])%mod;
                }
            }
        }
        int ans=1;int ans2=0;
        for(int i=1;i<=m;i++)
            ans=(ans*26)%mod;
        for(int i=0;i<=tot;i++)
            if(!visit[i])
            ans2=(ans2+dp[m][i])%mod;
        return (ans-ans2+mod)%mod;
    }
    int main()
    {
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            init();
            for(int i=1;i<=n;i++)
            {
                scanf("%s",t);
                build_trie(t);
            }
            build_fail();
            cout<<solve()<<endl;
        }
    }

转载于:https://www.cnblogs.com/huangdao/p/10849233.html