[IOI 1996 / USACO2.3] 最长前缀 Longest Prefix
用前缀可达性 DP 判断序列能否由原串重复拼成，后缀是否为词用哈希集合或倒序 Trie 查询。
OJ: luogu
题目 ID: P1470
难度:普及/提高-
标签:动态规划字符串defaultdictpython
日期: 2026-07-16 19:57
题意
给定最多 200 个短原串，它们可以重复使用。求目标序列能由这些原串拼出的最长前缀长度。
思路
令 dp[i] 表示前缀 S[0..i) 能否由词集完整拆开，边界 dp[0]=true。
转移时枚举最后一个词的长度 len：若后缀 S[i-len..i) 是一个词，且 dp[i-len] 为真，则 dp[i]=true。词长最多 10，所以从 i 往回最多尝试 10 个长度，而不是遍历全部原串。
“后缀是否是词”有两种查询方式：
- 哈希：
hash.cpp直接用unordered_set存词，构造子串后查询，实现最简单。 - 有序集合：
set.cpp用set<string>存词，查询O(log |P|)次字符串比较；词集只有 200 个、词长不超过 10，开销可忽略。 - 倒序 Trie：
trie.cpp把每个词反着插入，让S从i往回走，边走边判断；走不动时说明不存在更长的候选词，直接剪枝。
注意 dp[i] 并不是单调的（例如 i 可达不代表 i+1 可达），所以答案要取所有可达位置的最大值。
Python 知识
tokens.index(b".")找到原串区与目标串的分隔符。defaultdict(set)同时完成按长度分组和去重。b"".join(...)拼回跨多行输入的目标序列。bytearray(n+1)是紧凑的布尔 DP 数组。
代码
python
import sys
from collections import defaultdict
# 读入全部输入并按空白切分，得到字节 token 列表
tokens = sys.stdin.buffer.read().split()
# 分隔符 b"." 之前是原串，之后是目标序列
separator = tokens.index(b".")
primitives_by_length = defaultdict(set)
for primitive in tokens[:separator]:
primitives_by_length[len(primitive)].add(primitive)
sequence = b"".join(tokens[separator + 1:])
n = len(sequence)
# dp[i] 表示前缀 sequence[0..i) 能否由原串完整拼出
dp = bytearray(n + 1)
dp[0] = 1 # 空前缀一定能拼出
answer = 0
# 与 C++ 的写法一致：站在位置 i，往回找最后一个词
for i in range(1, n + 1):
# 枚举最后一个词的长度 length（原串最长 10 个字符）
for length in range(1, 11):
start = i - length
if start < 0:
continue
if length not in primitives_by_length:
continue
# 两个条件同时满足：前缀 sequence[0..start) 能拼出，
# 且后缀 sequence[start..i) 是一个原串
if dp[start] and sequence[start:i] in primitives_by_length[length]:
dp[i] = 1
break # 找到一个拆法即可，不需要继续尝试更长或更短的词
if dp[i]:
answer = max(answer, i) # dp 不单调，取所有可达位置的最大值
print(answer)哈希查询版本的 C++ 实现：
cpp
#include <bits/stdc++.h>
using namespace std;
// ============ 哈希解法 ============
// 与 trie.cpp 完全相同的 DP 思路，区别只在于"后缀是否在词集中"的查找方式：
// trie.cpp：倒序 Trie，从位置 i 往回走，边走边判断，可提前剪枝
// 本文件： unordered_set，直接构造子串 S.substr(i-len, len) 后查集合
// 词长 <= 10，两种方式每个位置都只需 O(10)，复杂度同为 O(10*|S|)。
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 读入词集 P：以单独一行 "." 结束
unordered_set<string> words;
string word;
while (cin >> word && word != ".") {
words.insert(word);
}
// 读入 S：每 76 个字符一行，必须拼成完整串
string S, line;
while (cin >> line) S += line;
int n = (int)S.size();
vector<char> dp(n + 1, false);
dp[0] = true; // 空前缀可拆
int ans = 0;
for (int i = 1; i <= n; i++) {
// 枚举最后一个词的长度 len（词长 <= 10）
for (int len = 1; len <= 10 && i - len >= 0; len++) {
// 两个条件同时满足：后缀是词，且前缀 S[0..i-len) 能拆开
if (dp[i - len] && words.count(S.substr(i - len, len))) {
dp[i] = true;
break; // 找到一个拆法即可
}
}
if (dp[i]) ans = i; // dp 不单调，取所有可达位置的最大值
}
cout << ans << '\n';
return 0;
}有序集合版本的 C++ 实现：
cpp
/**
* 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-08-01 23:57
* update_at: 2026-08-01 23:57
*/
// ============ set 解法 ============
// 与 hash.cpp 完全相同的 DP 思路，区别只在于"后缀是否在词集中"的查找方式：
// hash.cpp：unordered_set，哈希查询，平均 O(1)
// 本文件： set<string>，有序集合，查询 O(log |P|) 次字符串比较
// 词集只有最多 200 个词、词长 <= 10，红黑树查询的开销可以忽略。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 读入词集 P：以单独一行 "." 结束
set<string> words;
string word;
while (cin >> word && word != ".") {
words.insert(word);
}
// 读入 S：每 76 个字符一行，必须拼成完整串
string S, line;
while (cin >> line) S += line;
int n = (int)S.size();
vector<char> dp(n + 1, false);
dp[0] = true; // 空前缀可拆
int ans = 0;
for (int i = 1; i <= n; i++) {
// 枚举最后一个词的长度 len（词长 <= 10）
for (int len = 1; len <= 10 && i - len >= 0; len++) {
// 两个条件同时满足：后缀是词，且前缀 S[0..i-len) 能拆开
if (dp[i - len] && words.count(S.substr(i - len, len))) {
dp[i] = true;
break; // 找到一个拆法即可
}
}
if (dp[i]) ans = i; // dp 不单调，取所有可达位置的最大值
}
cout << ans << '\n';
return 0;
}倒序 Trie 版本的 C++ 实现：
cpp
#include <bits/stdc++.h>
using namespace std;
// ============ 倒序 Trie ============
// 需求：给定字符串 S 和位置 i，快速找出"以 S[i] 结尾、且在词集 P 中"的所有后缀。
// 普通 Trie 从根出发表示"前缀"，无法直接回答"后缀"；把每个词反着插入，
// 再让 S 从后往前走，就能从根一路判断后缀是不是词。
struct Trie {
struct Node {
array<int, 26> ch{}; // ch[c] 子节点编号，0 为空（根也是 0）
int end = 0; // 以该节点结尾的完整词个数
};
vector<Node> tree; // tree[0] 为根
Trie() { tree.push_back(Node()); }
// 倒着插入：把 s 反串放进 Trie。例如 "AB" 存成根->B->A
void insert(const string &s) {
int u = 0;
for (int i = (int)s.size() - 1; i >= 0; i--) {
int c = s[i] - 'A';
if (tree[u].ch[c] == 0) { // 无子节点则新建
tree[u].ch[c] = (int)tree.size();
tree.push_back(Node());
}
u = tree[u].ch[c];
}
tree[u].end++; // 走到词尾，标记为一个完整词
}
};
// ============ 主程序 ============
// 思路：dp[i] 表示前缀 S[0..i) 能否由词集 P 完整拆开。
// 转移：枚举最后一个词 w，要求 S 以 i 结尾的后缀 == w，且 dp[i-|w|] 为真。
// 词长 <= 10，所以从 i 往回最多试 10 个长度。
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 读入词集 P：以单独一行 "." 结束（"." 之前可能有多行）
Trie trie;
string word;
while (cin >> word && word != ".") {
trie.insert(word);
}
// 读入 S：每 76 个字符一行，必须拼成完整串
string S, line;
while (cin >> line) S += line;
int n = (int)S.size();
vector<char> dp(n + 1, false);
dp[0] = true; // 空前缀可拆
int ans = 0;
for (int i = 1; i <= n; i++) {
// 从 i 往前，在倒序 Trie 上连续走，len 是当前后缀长度
int u = 0;
for (int len = 1; len <= 10 && i - len >= 0; len++) {
int c = S[i - len] - 'A';
// 走不动了：不可能有更长的反串前缀，直接剪枝
if (trie.tree[u].ch[c] == 0) break;
u = trie.tree[u].ch[c];
// 当前后缀 S[i-len..i) 是一个完整词，且前面部分能拆开
if (trie.tree[u].end && dp[i - len]) {
dp[i] = true;
break; // 找到一个拆法即可
}
}
if (dp[i]) ans = i; // dp 不单调，取所有可达位置的最大值
}
cout << ans << '\n';
return 0;
}复杂度
最多 10 种长度，时间
总结
“按长度分组为集合”是 Python 处理许多短模式串时很实用的优化。