P4052[JSOI2007]文本生成器

· · 题解

这道题，人人都说是AC自动机上dp的套路板子，但是他们给的分析蒟蒻死活也听不明白(可能是初学的缘故.......)

好久终于搞懂了，写了这篇题解想造福跟我一样的同胞(应该只有我一个人这么菜......)

题意简化　：

给你n个模式串，你需要生成一个长度为m的字符串使得至少一个模式串可以匹配成功，问可行的生成方案总数对10007取模。

多串匹配，计数，是dp + AC自动机.....(这里还是蛮显然的)

但是怎么做?

思路

什么样的字符串使得至少一个模式串可以匹配？这个东西太难处理了。

正难则反 --------- OI中的著名四字成语

不妨转化为求没有一个模式串可以匹配成功的方案数为sum。(补集转换)

然后不含一个模式串的字符串的方案就是26^m - sum

首先用n个模式串模式串建立一个AC自动机

思考什么时候会有一个文本串使得没有一个模式串可以匹配成功？
//这是AC自动机进行匹配的代码。
//这段函数将会输出有多少个模式串与文本串匹配成功
void GetAns()
{
    int len = strlen(a),now = 0 , ans = 0;
    for(int i = 0 ; i < len  ; i ++)
    {
        int num = a[i] - 'a';
        now = AC[now].son[num];
        for(int u = now ; AC[u].end != -1 && u ; u = AC[u].Fail)
        {
            ans += AC[u].end;
            AC[u].end = -1;
        }
    }
    cout << ans << endl;
    return ;
}

观察ＡＣ自动机获取答案的过程，我们发现:

访问到一个文本串里面的节点，我们就会不停的跳这个点的Fail，这个点的Fail的Fail .......(这个就被称为Fail链)，直到跳到根或者是答案已经被计算过的点(已经被跳过了，再往下跳就重复了)。

然后答案累加上以跳到的点为结尾的模式串的个数。

假设i的Fail指针指向点j，根据Fail指针的定义就为：Ｔｒｉｅ上根节点到j的路径形成的字符串是Ｔｒｉｅ上根节点到i的路径形成的字符串的后缀

那么这样子答案是显然可行的.

那么我们要让答案为0，怎么办?

那就是当前点以及跳到的点上，没有任何一个模式串以它们为结尾，我们要选的点是这些，至于其他的点，我们则要"避开"。

考虑如何DP

根据套路(没办法，套路还是得知道一下的)，ＡＣ自动机上的ＤＰ一般状态的设置是这样子的: DP[i][j] <-----　表示AC自动机上走i步且最后走的一个是j的答案

根据上面的分析DP[i][k] 就要累加上 DP[i - 1][j] (k是j的儿子，同时满足j没有一个模式串以其Fail链上的点(包括j)为结尾)

最后，统计出来所有的答案\sum_{i = 0}^{i = cnt} {DP[m][i]}也就是以ＡＣ自动机上任意一个节点为"j"的答案，同时文本要求长度为m

答案就是(26^m - sum) mod 10007

至此结束.

注意一下模意义下减法要加上Mod防止变成负数,详见代码。

Code

#include <bits/stdc++.h>
using namespace std;
int n,m,cnt = 0;
const int MAXN = 6005,MAXM = 105,Mod = 10007;//常量赋值
char s[1005];//给定的模式串用这个存
struct node{
    int end,Fail;
    int son[26];
}AC[MAXN];//AC自动机
int vis[MAXN];//建立Fail指针的时候要用的东西
int f[MAXM][MAXN];//DP数组
void build()
{
    int len = strlen(s),now = 0;
    for(int i = 0 ; i < len ; i ++)
    {
        int num = s[i] - 'A';
        if(AC[now].son[num] == 0)
            AC[now].son[num] = ++cnt;
        now = AC[now].son[num];
    }
    AC[now].end = 1;
}//建立AC自动机

void GetFail()
{
    int now = 0 , head = 0 , tail = 0;
    for(int i = 0 ; i < 26 ; i ++)
        if(AC[0].son[i])
            tail ++ , vis[tail] = AC[0].son[i];
    while(head < tail)
    {
        head ++;
        int v = vis[head];
        for(int i = 0 ; i < 26 ; i ++)
        {
            if(AC[v].son[i])
            {
                AC[AC[v].son[i]].Fail = AC[AC[v].Fail].son[i];
                tail ++;
                vis[tail] = AC[v].son[i];//普通的建立AC自动机即可
                AC[AC[v].son[i]].end |= AC[AC[AC[v].son[i]].Fail].end;//这里运用了或运算来求出Fail链上是否有一个点为模式串的结尾
            }
            else AC[v].son[i] = AC[AC[v].Fail].son[i];
        }
    }
    return ;
}

int quick_power(int x,int y){
    int ans = 1 , op = x;
    if(y == 2)return x*x;
    if(x == 0)return 0;
    while(y){
        if(y % 2 == 1)ans *= op , ans %= Mod;
        op *= op , op %= Mod;
        y = y >> 1;
    }
    return ans % Mod;
}

void DP()
{
    f[0][0] = 1;
    for(int i = 1 ; i <= m ; i ++)
        for(int j = 0 ; j <= cnt ; j ++)
            if(!AC[j].end)//我们显然不能对不合法的点进行动态规划
            {
                for(int k = 0 ; k < 26 ; k ++)
                f[i][AC[j].son[k]] =( f[i][AC[j].son[k]] + f[i - 1][j] )% Mod;
            }
    int ans = 0;
    for(int j = 0 ; j <= cnt ; j ++)
        if(!AC[j].end)ans += f[m][j],ans %= Mod;
    cout <<(quick_power(26,m) - ans + Mod )% Mod;//这里要加上Mod，不然会死
}

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++)
    {
        cin >> s;
        build();
    }
    GetFail();//这里是进行建Fail的
    DP();//这里是进行DP的
    return 0;
}