这题有一个 AC 自动机的升级版：P2292 [HNOI2004] L 语言

非升级版的这道原题很容易想到：

• f[i] 表示前 i 个字符可否被理解
• f[i] = f[i] || (f[i-len] && i 结尾的长度为 len 个字符是一个单词)

用字典树判断是否是单词

#include <bits/stdc++.h>
using namespace std;
const int MAXNODE = 200; // 单词数*单词长度（最坏情况下节点数量）
int tot, root, son[MAXNODE + 5][26];
int tag[MAXNODE + 5]; // 存在几个单词
void clearNode(int nId)
{
    for (int i = 0; i < 26; i++)
        son[nId][i] = 0;
    tag[nId] = 0;
}
void ins(const string &s)
{
    int now = root;
    for (int i = 0; i < s.size(); i++)
    {
        int j = s[i] - 'a';
        if (!son[now][j])
        {
            son[now][j] = ++tot;
            clearNode(tot);
        }
        now = son[now][j];
    }
    tag[now]++;
}
// 检测 s 的第 l 个字符到第 r 个字符是不是字典树里的单词
bool check(const string &s, int l, int r)
{
    l--;
    r--;
    int now = root;
    for (int i = l; i <= r; i++)
    {
        int j = s[i] - 'a';
        // 如果要新建节点，那就不是单词
        if (!son[now][j])
            return false;
        now = son[now][j];
    }
    return tag[now] > 0;
}
int n, m;
string d[25];
string s[25];
int f[1024 * 1024 + 5]; // 1MB
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> d[i];
    for (int i = 1; i <= m; i++)
        cin >> s[i];
    // 构建字典
    tot = root = 1;
    for (int i = 1; i <= n; i++)
        ins(d[i]);
    // 处理每个文章
    for (int i = 1; i <= m; i++)
    {
        int ans = 0;
        f[0] = true;
        for (int j = 1; j <= s[i].length(); j++)
        {
            // f[j]: 长度为 j 是否能被理解
            f[j] = false;
            for (int len = 1; len <= min(10, j); len++)
            {
                if (f[j - len] && check(s[i], j - len + 1, j))
                {
                    f[j] = true;
                    break;
                }
            }
            if (f[j])
                ans = j;
        }
        cout << ans << "\n";
    }
    return 0;
}

用 unordered_set 判断是否是单词

#include <bits/stdc++.h>
using namespace std;
int n, m;
string d[25];
string s[25];
int f[1024 * 1024 + 5]; // 1MB
unordered_set<string> se;
// 检测 s 的第 l 个字符到第 r 个字符是不是字典树里的单词
bool check(const string &s, int l, int r)
{
    l--;
    r--;
    return se.find(s.substr(l, (r - l + 1))) != se.end();
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> d[i];
    for (int i = 1; i <= m; i++)
        cin >> s[i];
    // 构建set
    for (int i = 1; i <= n; i++)
        se.insert(d[i]);
    // 处理每个文章
    for (int i = 1; i <= m; i++)
    {
        int ans = 0;
        f[0] = true;
        for (int j = 1; j <= s[i].length(); j++)
        {
            // f[j]: 长度为 j 是否能被理解
            f[j] = false;
            for (int len = 1; len <= min(10, j); len++)
            {
                if (f[j - len] && check(s[i], j - len + 1, j))
                {
                    f[j] = true;
                    break;
                }
            }
            if (f[j])
                ans = j;
        }
        cout << ans << "\n";
    }
    return 0;
}