「一本通 2.3 练习 2」L 语言

形式化题目

给定一个包含 $n$ 个单词的字典 $D$ 。若一段长度为 $L$ 的文本字符串 $T$ 可以被完整划分为若干个连续子串，且每一个子串都是 $D$ 中的单词，则称该字符串在字典 $D$ 下是可以被理解的。

现给出 $m$ 段待测试的文章，对于每段文章，求出其能够被字典 $D$ 理解的最长前缀的长度。

约束

$1 \leqslant n, m \leqslant 20$
单词长度不超过 $10$
文章长度至多 $1\text{ MB}$ （约 $10^6$ 字符）

正解

思路

这是一道经典的字符串可达性动态规划问题。

1. 状态定义

设文章长度为 $L$ 。定义布尔状态数组 $f$ ，其中：

$f[i] = 1$ 表示长度为 $i$ 的前缀 $T[0:i]$ 能够被字典中的单词完全拼接拆分。
初始时， $f[0] = 1$ （长度为 0 的空前缀天然可被理解）。

2. 状态转移

若前缀 $T[0:i]$ 可被理解（即 $f[i] = 1$ ），则可以从下标 $i$ 开始尝试匹配字典中的单词。设从位置 $i$ 开始匹配到了字典中的某个单词 $w$ ，其长度为 $|w|$ ，则说明前缀 $T[0:i+|w|]$ 也可以被理解，从而有状态转移：

f[i + |w|] = 1

因为字典中单词长度满足 $|w| \leqslant 10$ ，单词最大长度记为 $L_{\max} \leqslant 10$ 。我们可以把所有字典单词预先构建成一棵 Trie（字典树）。当遍历到任意一个可达的前缀位置 $i$ （ $f[i] = 1$ ）时，以 $T[i]$ 为起点在 Trie 上匹配后继字符：

沿着 Trie 转移，每次到达一个单词的终止节点（即存在单词以该字符结尾），便将对应的后继前缀位置置为 $1$ ；
若遇到 Trie 中没有的字符分支，则说明无法继续匹配更长的单词，立刻退出本次字符延伸。

3. 核心剪枝与提前终止

由于单词长度不超过 $L_{\max}$ ，若连续超过 $L_{\max}$ 个位置都不可达（即对于当前扫描位置 $i$ ，最近的一个可达位置 $last$ 满足 $i - last > L_{\max}$ ），那么从 $last$ 处无论选择字典里的哪一个单词，长度都不足以跨过这片空白区域达到位置 $i$ 及之后。此时后续所有位置必然全部不可达，可以直接提前退出遍历。

最终能够被理解的最长前缀长度即为所有满足 $f[i] = 1$ 的最大下标 $i$ 。

4. 样例推演与状态转移示例

以样例字典 $D = \{\text{is}, \text{name}, \text{what}, \text{your}\}$ 及文本 whatisyouname 为例：

前缀长度 $i$	前缀子串	是否可达 $f[i]$	匹配单词及推进
0	空串	1	匹配 `what`，标记 $f[4] = 1$
1~3	`w`, `wh`, `wha`	0	不可达，跳过
4	`what`	1	匹配 `is`，标记 $f[6] = 1$
5	`whati`	0	不可达，跳过
6	`whatis`	1	从位置 6 (`you...`) 匹配，字典无对应单词，无法推进
7~10	…	0	连续不可达，超过最长单词长度 4，提前终止

最长可理解的前缀长度为 6（对应前缀 whatis）。

flowchart LR
    A["0: 空串 (f[0]=1)"] -->|"what (长 4)"| B["4: what (f[4]=1)"]
    B -->|"is (长 2)"| C["6: whatis (f[6]=1)"]
    C -. "you 未在字典中" .-> D["失配，最大可达位置为 6"]

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 13:15
# update_at: 2026-09-30 13:15

import sys

TERMINAL = "#"  # 字典树单词终止标记


def build_trie(words: list[str]) -> dict:
    """构建字典树，节点包含子字符映射及终止标记。"""
    trie: dict = {}
    for word in words:
        node = trie
        for ch in word:
            node = node.setdefault(ch, {})
        node[TERMINAL] = True
    return trie


def longest_prefix(text: str, trie: dict, max_len: int) -> int:
    """计算单个文本在字典树下能被完全拆分理解的最长前缀长度。"""
    length = len(text)
    reach = bytearray(length + 1)
    reach[0] = 1
    last_reach = ans = 0

    for i in range(length + 1):
        if not reach[i]:
            if i - last_reach > max_len:  # 连续空隙超过最长单词，后续前缀必不可达
                break
            continue

        last_reach = ans = i
        node = trie
        for j in range(i, min(i + max_len, length)):
            ch = text[j]
            if ch not in node:
                break
            node = node[ch]
            if TERMINAL in node:
                reach[j + 1] = 1

    return ans


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())

    n = int(next(data))
    m = int(next(data))
    words = [next(data).decode() for _ in range(n)]
    texts = [next(data).decode() for _ in range(m)]

    trie = build_trie(words)
    max_len = max(len(w) for w in words) if words else 0
    ans = [longest_prefix(text, trie, max_len) for text in texts]

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 03:21
 * update_at: 2026-10-05 03:21
 */
#include <cstring>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXNODE = 205;    // 字典树节点上限：20 个单词，每个单词长度不超过 10
const int MAXLEN = 1000005; // 单篇文章长度上限 1 MB

int trie_next[MAXNODE][26]; // trie_next[u][c]：节点 u 沿字符 c 走到的子节点，0 表示没有该分支
int is_end[MAXNODE];        // is_end[u] = 1 表示节点 u 是某个单词的结尾
char reach[MAXLEN];         // reach[i] = 1 表示文章长度为 i 的前缀可以被字典完整拆分
char text[MAXLEN];          // 当前处理的文章

ll n, m;
int node_cnt = 0;     // 0 号节点是字典树的根
int max_word_len = 0; // 字典中最长单词的长度，用来限制匹配步数和剪枝

// 把单词 w 插入字典树。
void insert_word(const char *w) {
    int u = 0;
    for (int i = 0; w[i] != '\0'; i++) {
        int c = w[i] - 'a';
        if (trie_next[u][c] == 0) {
            node_cnt++;
            trie_next[u][c] = node_cnt;
        }
        u = trie_next[u][c];
    }
    is_end[u] = 1;
}

// 计算当前文章能被字典理解的最长前缀长度。
int longest_prefix() {
    int len = strlen(text);
    for (int i = 0; i <= len; i++) {
        reach[i] = 0;
    }
    reach[0] = 1; // 空前缀天然可以被理解

    int last_reach = 0; // 最近一个可达前缀的位置
    int ans = 0;
    for (int i = 0; i <= len; i++) {
        if (reach[i] == 0) {
            // 连续超过最长单词长度都没有可达位置，后面任何位置都不可能可达，直接结束
            if (i - last_reach > max_word_len) {
                break;
            }
            continue;
        }

        last_reach = i;
        ans = i;

        // 从位置 i 出发沿字典树匹配，最多前进 max_word_len 步
        int u = 0;
        for (int j = i; j < len && j < i + max_word_len; j++) {
            int c = text[j] - 'a';
            if (trie_next[u][c] == 0) {
                break;
            }
            u = trie_next[u][c];
            if (is_end[u]) {
                reach[j + 1] = 1;
            }
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    char word[16]; // 单词长度不超过 10
    for (ll i = 1; i <= n; i++) {
        cin >> word;
        int wlen = strlen(word);
        if (wlen > max_word_len) {
            max_word_len = wlen;
        }
        insert_word(word);
    }

    for (ll i = 1; i <= m; i++) {
        cin >> text; // text 已按 1 MB 上限开足
        cout << longest_prefix() << "\n";
    }

    return 0;
}

复杂度

时间复杂度：构建 Trie 树耗时 $O(\sum |w|)$ ，由于 $\sum |w| \leqslant 20 \times 10 = 200$ ，建树几乎瞬时完成。对长度为 $L$ 的文章，只有在 $f[i] = 1$ 时才沿 Trie 向后扫描至多 $L_{\max} \leqslant 10$ 步，每次仅需一步常数转移；配合不可达间隙剪枝，整体匹配时间为 $O(m \cdot L \cdot L_{\max})$ 。即使在 $1\text{ MB}$ 级别数据下，也能在 1 秒左右完成。
空间复杂度：Trie 树规模不超过 200 个节点；采用 bytearray(L + 1) 记录前缀可达性，占用内存仅约 $1\text{ MB}$ ，空间复杂度为 $O(L + \sum |w|)$ ，远低于 $128\text{ MB}$ 的限制。

总结

本题利用“单词数量少、单词长度极短（ $\leqslant 10$ ）”的数据特征，将文章的拆分理解问题建模为正向推进的前缀可达性 DP。利用 Trie 树加速多模式匹配，并将转移距离严格限制在 10 步以内，辅以可达间隙超长立即终止的剪枝，使得长达数兆字节的文本能在极短时间内完成判定。