bzoj 1030: [JSOI2007]文本生成器

.

题意：所有长度为m的字符串中有多少个字符串包括至少一个给出的单词
题解：AC自动机上DP
首先把问题转化成求有多少个不包含单词的字符串，答案用$26^m$减去就好了。不包括单词的字符串数量就相当于在AC自动机上从根出发有多少条路径不经过单词结尾的标记。设f[i][j]表示走了i步当前在j节点的路径数。枚举下一位填什么，像做字符串匹配一样跳fail，如果那个位置没有结尾标记，就更新那个节点（f[i+1][k]+=f[i][j]）。答案=$26^m-\sum^{num}_{i=0} f[m][i]$
代码：

#include<bits/stdc++.h>
using namespace std;

int n,m;
struct trie
{
    int s[26],fail;
    bool c;
}tr[60010];
int root=0,num=0,f[110][60010];
const int mod=10007;

void ins(char*s)
{
    int len=strlen(s);
    int now=root;
    for(int i=0;i<len;i++)
    {
        if(!tr[now].s[s[i]-'A'])
        tr[now].s[s[i]-'A']=++num;
        now=tr[now].s[s[i]-'A'];
    }
    tr[now].c=1;
}
void bfail()
{
    queue<int>q;
    for(int i=0;i<26;i++)
    if(tr[root].s[i])
    q.push(tr[root].s[i]);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(!tr[x].s[i])
            continue;
            int j=tr[x].fail;
            while(j&&!tr[j].s[i])
            j=tr[j].fail;
            if(tr[j].s[i])
            j=tr[j].s[i];
            tr[tr[x].s[i]].fail=j;
            q.push(tr[x].s[i]);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        char s[110];
        scanf("%s",s);
        ins(s);
    }
    bfail();
    f[0][0]=1;
    for(int i=0;i<m;i++)
    for(int j=0;j<=num;j++)
    {
        for(int k=0;k<26;k++)
        {
            int now=j;
            while(now&&!tr[tr[now].s[k]].c)
            now=tr[now].fail;
            if(tr[tr[now].s[k]].c)
            continue;
            now=j;
            while(now&&!tr[now].s[k])
            now=tr[now].fail;
            // if(tr[now].s[k])
            f[i+1][tr[now].s[k]]=(f[i+1][tr[now].s[k]]+f[i][j])%mod;
        }
    }
    int hh=1;
    for(int i=0;i<m;i++)
    hh=hh*26%mod;
    int oo=0;
    for(int i=0;i<=num;i++)
    oo=(oo+f[m][i])%mod;
    printf("%d\n",(hh-oo+mod)%mod);
}