[JSOI2007]文本生成器

· · 题解

这是一道简单的AC自动机上的DP问题。适合入门

文本生成器

乍一看，这是和字符串、计数有关的题。于是容易联想到AC自动机和DP。但是具体如何做呢？看到这句话“如果一篇文章中至少包含使用者们了解的一个单词”，容易联想到正难则反。只要求出有多少个一个认识的单词都没有的文章数即可。更具体的，首先建立AC自动机，然后设f[i][j]表示匹配到自动机上第i个结点，长度为j的字符串有多少个。初始状态，f[root][0]=0。每一次转移，可以从f[i][j]->f[son[i][k]][j+1]，即为每次走到一个儿子上。一个结点可以走，当且仅当这个节点的fail指针，以及fail指针的fail指针 \cdots\cdots 都不能是一个认识的单词的结尾。

于是这道题就结束了

#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

//1.常量设计
const int maxWord = 70, maxLen = 110, maxNode = 70 * 110, mod = 10007;
//2.变量的定义（变量类型）
int wordN = 0, totNode = 0;
queue<int> que;
//3.数组的定义
//4.数组的空间分配
int ch[maxNode][26] = {};
int fail[maxNode] = {}, dp[maxNode][maxLen] = {};
int createLen = 0;
bool can[maxNode] = {};
char input[maxLen] = {};
//5.变量的初始化
//6.函数的定义
void insert() {
    int now = 0, len = strlen(input + 1);
    for (int fuI = 1; fuI <= len; ++fuI) {
        int erZi = input[fuI] - 'A';
        if (!ch[now][erZi]) ch[now][erZi] = ++totNode;
        now = ch[now][erZi];
    }
    can[now] = 0;
}
void buildFail() {
    while (!que.empty()) que.pop();
    for (int erZi = 0; erZi < 26; ++erZi) if (ch[0][erZi]) que.push(ch[0][erZi]);
    while (!que.empty()) {
        int now = que.front();
        que.pop();
        for (int id = 0; id < 26; ++id) {
            if (ch[now][id]) {
                fail[ch[now][id]] = ch[fail[now]][id];
                if (!can[fail[ch[now][id]]]) can[ch[now][id]] = 0;
                que.push(ch[now][id]);
            } else {
                ch[now][id] = ch[fail[now]][id];
            }
        }
    }
}
void add(int &fir, int sec) {
    fir = (fir + sec) % mod;
}
void Minus(int &fir, int sec) {
    fir = ((fir - sec) % mod + mod) % mod;
}

int main()
{
    freopen("create.in", "r", stdin);
    freopen("create.out", "w", stdout);
    scanf("%d%d", &wordN, &createLen);
    for (int node = 0; node <= 60 * 100; ++node) can[node] = 1;
    for (int renShi = 1; renShi <= wordN; ++renShi) {
        scanf("%s", input + 1);
        insert();
    }
    buildFail();
    dp[0][0] = 1;
    for (int nowLen = 0; nowLen < createLen; ++nowLen) {
        for (int node = 0; node <= totNode; ++node) {
            if (!(dp[node][nowLen] && can[node])) continue;
            for (int sonId = 0; sonId < 26; ++sonId) {
                if (!can[ch[node][sonId]]) continue;    //注意这里转移到的点也要合法，不只是更新别人的点要合法
                add(dp[ch[node][sonId]][nowLen + 1], dp[node][nowLen]);
            }
        }
    }
    int ans = 1;
    for (int weiI = 1; weiI <= createLen; ++weiI) ans = (ans * 26) % mod;
    for (int endNode = 0; endNode <= totNode; ++endNode) {
        Minus(ans, dp[endNode][createLen]);
    }
    printf("%d\n", ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}