【JSOI2007】文本生成器 题解（AC自动机+动态规划）

题目链接

题目大意：给定$n$个子串，要求构造一个长度为$m$的母串使得至少有一个子串是其子串。问方案数。

------------------------

我们可以对要求进行转化：求出不合法的方案数，总方案数减去不合法的方案数即为合法方案数。

首先建一个AC自动机，对于每个串的末尾结点及其$fail$边指向的结点都打上标记，表示遍历AC自动机的时候不经过这些点（因为如果一个串是另一个串的后缀，显然这两个串都是合法的）。

然后就可以大力DP了。设$f[i][j]$表示走了$i$步到达$j$结点的方案数。则有转移方程$f[i+1][son(j)]+=f[i][j]$。答案即为$m^{26}-\sum\limits_{i=1}^{cnt} f[m][i]$。

代码：

#include<bits/stdc++.h>

using namespace std;

const int mod=1e4+;

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

string ss;

struct node

{

    int ch[],end,fail;

}tree[];

inline void build(string s)

{

    int l=s.length(),now=;

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

    {

        if (!tree[now].ch[s[i]-'A']) tree[now].ch[s[i]-'A']=++cnt;

        now=tree[now].ch[s[i]-'A'];

    }

    tree[now].end=;

}

inline void getfail()

{

    queue<int> q;

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

    {

        if (tree[].ch[i]) tree[].fail=,q.push(tree[].ch[i]);

    }

    while(!q.empty())

    {

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

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

        {

            if (!tree[now].ch[i])

            {

                tree[now].ch[i]=tree[tree[now].fail].ch[i];

                continue;

            }

            tree[tree[now].ch[i]].fail=tree[tree[now].fail].ch[i];

            q.push(tree[now].ch[i]);

            tree[tree[now].ch[i]].end|=tree[tree[tree[now].fail].ch[i]].end;

        }

    }

}

int main()

{

    cin>>n>>m;

    for (int i=;i<=n;i++) cin>>ss,build(ss);

    tree[].fail=;

    getfail();

    f[][]=;

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

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

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

                if (!tree[tree[j].ch[k]].end)

                    f[i][tree[j].ch[k]]+=f[i-][j],f[i][tree[j].ch[k]]%=mod;

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

    for (int i=;i<=cnt;i++) sum+=f[m][i];

    printf("%d",((ans-sum)%mod+mod)%mod);

    return ;

}