把一种含义看成若干互不重叠的 t 匹配,用前缀函数求出 t 在 s 中的全部结束位置,再按最右匹配分类做线性 DP 统计。
OJ: roj
题目 ID: 1697
难度:普及+/提高-
标签:字符串KMP动态规划python
创建: 2026-10-07 15:47
更新: 2026-10-07 15:47
形式化题目
给定串
求
以第一组样例
正解
思路
第一步:把"含义"翻译成计数对象。 一个字符在同一时刻只能有一种解读,所以两个覆盖到同一字符的重叠匹配不可能同时取深意——若同时取深意,那段重叠的字符要同时属于两个
第二步:找出所有匹配。 这是 KMP 的看家本领:先对
第三步:数不重叠匹配族。 设
很多互不重叠的子集计数都可以按"最靠右的那一个匹配"分类,本题同样:考虑前
- 若
按原意解读(即没有任何取深意的匹配以 结尾),方案数与 一一对应; - 若某个取深意的匹配恰好结束于
,则它必然是区间 (结束位置唯一决定这个匹配),而剩下那些取深意的匹配必须全部落在 内,方案数为 。
两类的并恰好覆盖全部方案、交集为空,所以
答案即
回到样例
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| 结束于 |
— | — | — | — | ✓ | — | ✓ | — | ✓ |
| — | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | |
| — | — | — | — | — | — | ||||
| 1 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 5 |
第 4 格首次出现匹配:
实现要点。 ends[i] 是布尔标记,用 char 数组存 fail、ends、dp 都只在下标 ends 每轮只需清 t + '\x00' + s 拼串后求前缀函数,一次扫描同时得到全部匹配位置,
避免手写 KMP 的两段循环。
代码
Python 版:
#!/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-10-07 15:47
# update_at: 2026-10-07 15:47
import sys
MOD = 1000000007 # 答案对 1e9+7 取模
type Ends = list[bool] # ends[i] = s 的前 i 个字符是否恰好以 t 结尾
def matched_ends(s: str, t: str) -> Ends:
"""线性时间标记 t 在 s 中的每一次出现(允许重叠),返回按结束位置索引的布尔表。"""
m = len(t)
# 一次前缀函数求出全部匹配:拼成 t + 分隔符 + s,分隔符取小写字母之外的字符,
# 这样前缀长度永远跨不过分隔符,等于 m 的位置就是一次完整匹配。
text = t + '\x00' + s
pi = [0] * len(text)
ends: Ends = [False] * (len(s) + 1)
for i in range(1, len(text)):
j = pi[i - 1]
while j and text[i] != text[j]:
j = pi[j - 1]
if text[i] == text[j]:
j += 1
pi[i] = j
if j == m: # 前缀函数涨到 m,说明此处恰好匹配了一整个 t
ends[i - m] = True # text 下标 i 换成 s 的 1 起结束位置就是 i - m
return ends
def count_meanings(s: str, t: str) -> int:
"""按「最靠右的那个取深意的匹配」分类,用 dp 统计互不重叠的匹配组数。"""
ends = matched_ends(s, t)
m = len(t)
# dp[i] = 前 i 个字符的含义种数,dp[0] = 1;要回退 m 格,所以整张表要留着
dp: list[int] = [1]
for i in range(1, len(s) + 1):
best = dp[i - 1] # 没有匹配结束在 i:末段取原意
if ends[i]:
best = (best + dp[i - m]) % MOD # 末尾这段 t 取深意,前面随意
dp.append(best)
return dp[-1]
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
T = int(next(data))
out: list[str] = []
for _ in range(T):
s = next(data).decode() # 题面的 s
t = next(data).decode() # 题面的 t
out.append(str(count_meanings(s, t)))
sys.stdout.write('\n'.join(out) + '\n')
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 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-07 15:47
* update_at: 2026-10-07 15:47
*/
// 一本通 1697《深意》:单词 t 有原意与"深意"两种含义,串 s 中每一处出现的 t
// 都可以选择取哪种含义,问 s 一共有多少种含义。
//
// 模型:一种含义 = 一组两两不重叠的匹配位置(这组匹配取"深意",其余取原意)。
// 做法:KMP 求出 t 在 s 中的全部匹配的结束位置,再线性 DP 统计不重叠匹配组数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
const ll MAXN = 100005; // |s| 上限 1e5,见数据规模 len(t) <= len(s) <= 100000
char buf_s[MAXN]; // 当前这组的 s
char buf_t[MAXN]; // 当前这组的 t
int fail[MAXN]; // fail[i]:t 的前 i 个字符的最长"真前缀 = 后缀"长度
char occ[MAXN]; // occ[i]:s 的前 i 个字符恰好以 t 结尾;取值只有 0/1,用 char 省内存
ll dp[MAXN]; // dp[i]:s 的前 i 个字符能表示出的含义种数
// 求 t 的失配数组 fail(模式串自匹配)。
void build_fail(ll m) {
fail[0] = 0;
fail[1] = 0;
ll j = 0; // j:已经匹配上的 t 的前缀长度
for (ll i = 1; i < m; i++) {
while (j > 0 && buf_t[i] != buf_t[j]) j = fail[j];
if (buf_t[i] == buf_t[j]) j++;
fail[i + 1] = j;
}
}
// 标记 t 在 s 中的每一次出现:occ[i] = 1 表示子串 s[i-m .. i-1] 等于 t。
// 末尾出现过 t 的前缀才可能把最后一段取深意,所以只需记录结束位置。
void mark_occurrence(ll a, ll m) {
for (ll i = 0; i <= a; i++) occ[i] = 0; // 只清实际用到的范围 [0, a]
ll j = 0;
for (ll i = 0; i < a; i++) {
while (j > 0 && buf_s[i] != buf_t[j]) j = fail[j];
if (buf_s[i] == buf_t[j]) j++;
if (j == m) { // s[i-m+1 .. i] 匹配成功(此处按 1 起下标即结束位置 i+1)
occ[i + 1] = 1;
j = fail[j]; // 允许匹配区间重叠,继续往后找
}
}
}
// 统计 s 的含义种数:按"最后一个取深意的匹配的结束位置"对方案分类。
ll count_meanings(ll a, ll m) {
build_fail(m);
mark_occurrence(a, m);
dp[0] = 1; // 空前缀只有一种含义
for (ll i = 1; i <= a; i++) {
dp[i] = dp[i - 1]; // 没有匹配恰好结束在 i:末段取原意
if (occ[i]) dp[i] = (dp[i] + dp[i - m]) % MOD; // 末尾这段 t 取深意,前面部分随意
}
return dp[a];
}
int main() {
ll n;
if (scanf("%lld", &n) != 1) return 0;
for (ll k = 1; k <= n; k++) {
scanf("%s", buf_s);
scanf("%s", buf_t);
ll a = strlen(buf_s);
ll m = strlen(buf_t);
// 题面保证 m <= a;真出现更长的 t 则 occ 全为 0,答案自然是 1。
printf("%lld\n", count_meanings(a, m));
}
return 0;
}复杂度
- 时间:每组 KMP 为
,DP 为 ,合计 。 最大数据 、 ,总量约 次字符比较, C++ 实测远低于 1000 ms 限时。 - 空间:
,即 fail、ends、dp、两个字符串缓冲区, 常数量级约字节,远低于 256 MB。 - 与 C++ 解法的关系:
main.cpp是同一算法的 C++ 版本,KMP 与 DP 都是朴素循环; Python 版本靠"拼接串 + 前缀函数"把 KMP 压成一段循环,复杂度同阶。
总结
- 先读题面再写代码:本题的难点不在 KMP,而在把"含义"精确翻译成"互不重叠的匹配族"。
样例 3 的
种、样例 1 的 种都只能由这个模型解释;反过来,如果误以为重叠的匹配也能 同时取深意,样例 1 会算出 并被判错。 - 按"最右者"分类是计数类 DP 的通用套路。相邻位置不重叠的条件天然适合"最后一个元素"分类法:
最右匹配的结束位置唯一,于是分类既不重也不漏,转移只需回退
个字符。 - 模式匹配是线性 DP 的前置预处理:KMP 的
让"哪些位置是匹配"变成一张 表, 之后的 DP 就与字符串无关,退化成一维递推。 - 本题是"KMP + 线性 DP 计数不重叠匹配"的模板(同型题如 HDU 5763 Another Meaning)。
牢记模型后,把匹配条件从
换成任意可判定的区间条件,同一套 DP 依然适用。 - 本仓库素材里的
std.cpp与本解法同型(KMP + DP),已用它在全部 10 组真实数据上跑过, 输出与.out逐字节一致,可作算法参照;main.cpp按本 skill 的 C++ 风格重写,未照抄。
图示解析
下图把样例
flowchart LR
subgraph MATCH["s = hehehehe 的三个匹配"]
M1["s[1..4]"] --- M2["s[3..6]"]
M2 --- M3["s[5..8]"]
end
subgraph DP["dp 的转移:dp[i] += dp[i-m]"]
D0["dp[0] = 1"] --> D4["dp[4] = 2"]
D2["dp[2] = 1"] --> D6["dp[6] = 3"]
D4 --> D8["dp[8] = 5"]
end
左半边可以看出: