先用 Z 函数求每个位置和字典串前缀的最长匹配长度，再把这些匹配视作区间覆盖做最少跳数贪心。
OJ: luogu
题目 ID: P8112
难度:提高+/省选-
标签:字符串贪心Z函数区间覆盖
日期: 2026-06-21 12:51
题意
给一个字典串 T 和一个符文串 S。
题目保证：
T的所有非空前缀都是合法词缀
现在要把 S 划分成尽量少的若干段，每一段都必须是 T 的某个非空前缀。
如果无法划分，输出 Fake。
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int len_t, len_s;
string t, s;
cin >> len_t >> len_s;
cin >> t >> s;
int m = (int) t.size();
int n = (int) s.size();
vector<int> dp(n + 1, INF);
dp[0] = 0;
for (int i = 0; i < n; i++) {
if (dp[i] == INF) {
continue;
}
for (int len = 1; len <= m && i + len <= n; len++) {
bool same = true;
for (int j = 0; j < len; j++) {
if (s[i + j] != t[j]) {
same = false;
break;
}
}
if (same) {
dp[i + len] = min(dp[i + len], dp[i] + 1);
}
}
}
if (dp[n] == INF) {
cout << "Fake\n";
}
else {
cout << dp[n] << '\n';
}
return 0;
}因为合法词缀就是 T 的所有非空前缀，所以对 S 的每个起点 i，我们真正关心的只有一件事：
- 从这里开始，最多能匹配
T的前多少个字符
设这个最大长度是 reach[i]，那么从位置 i 出发，我们就可以任选一段：
- 长度在
[1, reach[i]]之间
如果把每个位置 i 看成一个区间：
- 可以覆盖到
i + reach[i]
那么题目就变成了：
- 用最少个区间，从位置
0一路覆盖到位置n
这就是经典的“最少跳数 / 区间覆盖”贪心。
接下来只剩如何快速求 reach[i]。
把字符串拼成：
T + '#' + S
对这个新串做一次 Z 函数，就能在线性时间求出：
S每个位置和T前缀的最长公共前缀长度
这正好就是 reach[i]。
最后做一遍最少跳数贪心：
- 当前已经覆盖到
cur_end - 扫描所有
i <= cur_end的位置，更新最远能到的far - 一次扩展结束后，把答案加一，并把
cur_end = far - 如果
far没有继续变大，说明无解
这样总复杂度就是线性的。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
string t, s;
// Z 函数：z[i] 表示 str[i..] 与 str[0..] 的最长公共前缀长度。
vector<int> z_function(const string &str) {
int len = (int) str.size();
vector<int> z(len, 0);
int l = 0, r = 0;
z[0] = len;
for (int i = 1; i < len; i++) {
if (i <= r) {
z[i] = min(r - i + 1, z[i - l]);
}
while (i + z[i] < len && str[z[i]] == str[i + z[i]]) {
z[i]++;
}
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int len_t, len_s;
cin >> len_t >> len_s;
cin >> t >> s;
int m = (int) t.size();
int n = (int) s.size();
string merged = t + "#" + s;
vector<int> zf = z_function(merged);
vector<int> reach(n, 0);
for (int i = 0; i < n; i++) {
reach[i] = min(zf[m + 1 + i], m);
}
// 把每个位置 i 看成一个区间 [i, i + reach[i]]。
// 问最少用多少段覆盖到 n，就是经典最少跳数贪心。
int ans = 0;
int cur_end = 0;
int far = 0;
int i = 0;
while (cur_end < n) {
while (i <= cur_end && i < n) {
far = max(far, i + reach[i]);
i++;
}
if (far <= cur_end) {
cout << "Fake\n";
return 0;
}
ans++;
cur_end = far;
}
cout << ans << '\n';
return 0;
}复杂度
Z 函数是
后面的最少跳数贪心也是
总复杂度
总结
这题最关键的转换是：
- 先把“每段必须是
T的前缀”转成“每个位置最多能走多远” - 再把整个问题转成区间覆盖最少段数
前半段用 Z 函数，后半段用贪心，两部分拼起来就是正解。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
