深意

GitHub跳转原题关系图返回列表

把一种含义看成若干互不重叠的 t 匹配,用前缀函数求出 t 在 s 中的全部结束位置,再按最右匹配分类做线性 DP 统计。

OJ: roj

题目 ID: 1697

难度:普及+/提高-

标签:字符串KMP动态规划python

创建: 2026-10-07 15:47

更新: 2026-10-07 15:47

形式化题目

给定串 ss(∣s∣=a|s| = a)与串 tt(∣t∣=m⩽a|t| = m \leqslant a),二者只含小写字母。 记 ss 中所有与 tt 相等的子串位置为匹配:若 s[i−m+1..i]=ts[i-m+1..i] = t,就说存在一个结束于 ii 的匹配。

ss 的一种含义由一族匹配的集合 SS 确定:SS 中任意两个匹配的区间互不重叠 (不共享任何字符),SS 中全部位置按"深意"解读,其余字符按"原意"解读。 等价地,每个匹配既可以取原意,也可以取深意,但同时取深意的两个匹配不能重叠。

求 ss 的不同含义个数,对 10000000071000000007 取模。共有 n⩽10n \leqslant 10 组询问。

以第一组样例 s=hehehes = \texttt{hehehe}、t=hehet = \texttt{hehe} 为例,tt 在 ss 中的匹配是 s[1..4]s[1..4] 与 s[3..6]s[3..6],二者重叠,因此可取深意的集合只有 ∅\varnothing、{s[1..4]}\{s[1..4]\}、{s[3..6]}\{s[3..6]\} 三种,答案为 33,与题面一致。

正解

思路

第一步:把"含义"翻译成计数对象。 一个字符在同一时刻只能有一种解读,所以两个覆盖到同一字符的重叠匹配不可能同时取深意——若同时取深意,那段重叠的字符要同时属于两个 tt,矛盾。反过来,任意一族两两不重叠的匹配都合法:把它们圈成深意、其余字符保留原意即可。于是答案就是

#{ S⊆所有匹配  ∣  S 中任意两区间不交 }.\#\{\,S \subseteq \text{所有匹配} \;\big|\; S \text{ 中任意两区间不交}\,\}.

第二步:找出所有匹配。 这是 KMP 的看家本领:先对 tt 求失配数组 fail[j]=\mathrm{fail}[j] = tt 的前 jj 个字符的最长"真前缀 = 真后缀"长度,再用它在 ss 上扫一遍。每匹配满 mm 个字符就记下结束位置 ii 并让 j←fail[m]j \leftarrow \mathrm{fail}[m],这样重叠的匹配(如 hehe\texttt{hehe} 在 hehehe\texttt{hehehe} 中的两次)一个都不会漏。

第三步:数不重叠匹配族。 设

dp[i]=只保留 s 的前 i 个字符时的含义数,dp[0]=1.dp[i] = \text{只保留 } s \text{ 的前 } i \text{ 个字符时的含义数},\qquad dp[0] = 1.

很多互不重叠的子集计数都可以按"最靠右的那一个匹配"分类,本题同样:考虑前 ii 个字符,

  • 若 s[i]s[i] 按原意解读(即没有任何取深意的匹配以 ii 结尾),方案数与 dp[i−1]dp[i-1] 一一对应;
  • 若某个取深意的匹配恰好结束于 ii,则它必然是区间 [i−m+1,i][i-m+1, i](结束位置唯一决定这个匹配),而剩下那些取深意的匹配必须全部落在 [1,i−m][1, i-m] 内,方案数为 dp[i−m]dp[i-m]。

两类的并恰好覆盖全部方案、交集为空,所以

dp[i]=dp[i−1]+ci⋅dp[i−m],ci={1,s[i−m+1..i]=t0,否则dp[i] = dp[i-1] + c_i \cdot dp[i-m], \qquad c_i = \begin{cases} 1, & s[i-m+1..i] = t \\ 0, & \text{否则} \end{cases}

答案即 dp[a]dp[a]。转移只用到 i−1i-1 与 i−mi-m,实现上用一个长度为 a+1a+1 的数组顺序推即可。

回到样例 s=hehehehes = \texttt{hehehehe}、t=hehet = \texttt{hehe},匹配结束于 4,6,84, 6, 8,逐格填表:

ii 0 1 2 3 4 5 6 7 8
结束于 ii 的匹配 — — — — ✓ — ✓ — ✓
dp[i−1]dp[i-1] — 1 1 1 1 2 2 3 3
dp[i−m]dp[i-m] — — — — dp[0]=1dp[0]=1 — dp[2]=1dp[2]=1 — dp[4]=2dp[4]=2
dp[i]dp[i] 1 1 1 1 2 2 3 3 5

第 4 格首次出现匹配:dp[4]=dp[3]+dp[0]=2dp[4] = dp[3] + dp[0] = 2,对应"全原意"与"s[1..4]s[1..4] 取深意"; 第 6 格 dp[6]=dp[5]+dp[2]=3dp[6] = dp[5] + dp[2] = 3,第 8 格 dp[8]=dp[7]+dp[4]=5dp[8] = dp[7] + dp[4] = 5, 共 55 种含义,与样例第 3 组的输出一致。注意 dp[4]dp[4] 被加进 dp[8]dp[8] 时值已经是 22, 它同时充当了"s[1..4]s[1..4] 取深意"与"s[1..4]s[1..4]、s[5..8]s[5..8] 都取深意"两条链条的起点。

实现要点。 ends[i] 是布尔标记,用 char 数组存 10510^5 量级的下标最省内存; fail、ends、dp 都只在下标 [0,∣s∣][0, |s|] 上有意义,ends 每轮只需清 a+1a+1 个位置。 Python 侧用 t + '\x00' + s 拼串后求前缀函数,一次扫描同时得到全部匹配位置, 避免手写 KMP 的两段循环。

代码

Python 版:

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++ 版(同一算法):

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-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 为 O(a+m)O(a + m),DP 为 O(a)O(a),合计 O(∑(a+m))O(\sum (a+m))。 最大数据 n=10n = 10、a=m=105a = m = 10^5,总量约 2×1062 \times 10^6 次字符比较, C++ 实测远低于 1000 ms 限时。
  • 空间:O(a+m)O(a + m),即 fail、ends、dp、两个字符串缓冲区, 常数量级约 105×410^5 \times 4 字节,远低于 256 MB。
  • 与 C++ 解法的关系:main.cpp 是同一算法的 C++ 版本,KMP 与 DP 都是朴素循环; Python 版本靠"拼接串 + 前缀函数"把 KMP 压成一段循环,复杂度同阶。

总结

  • 先读题面再写代码:本题的难点不在 KMP,而在把"含义"精确翻译成"互不重叠的匹配族"。 样例 3 的 55 种、样例 1 的 33 种都只能由这个模型解释;反过来,如果误以为重叠的匹配也能 同时取深意,样例 1 会算出 44 并被判错。
  • 按"最右者"分类是计数类 DP 的通用套路。相邻位置不重叠的条件天然适合"最后一个元素"分类法: 最右匹配的结束位置唯一,于是分类既不重也不漏,转移只需回退 mm 个字符。
  • 模式匹配是线性 DP 的前置预处理:KMP 的 O(a+m)O(a+m) 让"哪些位置是匹配"变成一张 0/10/1 表, 之后的 DP 就与字符串无关,退化成一维递推。
  • 本题是"KMP + 线性 DP 计数不重叠匹配"的模板(同型题如 HDU 5763 Another Meaning)。 牢记模型后,把匹配条件从 tt 换成任意可判定的区间条件,同一套 DP 依然适用。
  • 本仓库素材里的 std.cpp 与本解法同型(KMP + DP),已用它在全部 10 组真实数据上跑过, 输出与 .out 逐字节一致,可作算法参照;main.cpp 按本 skill 的 C++ 风格重写,未照抄。

图示解析

下图把样例 s=hehehehes = \texttt{hehehehe}、t=hehet = \texttt{hehe} 的匹配与 DP 画在一起: 上排是三个匹配区间,它们的重叠关系决定了哪些匹配能同时取深意;下排是 dpdp 的转移依赖。

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

左半边可以看出:s[1..4]s[1..4] 与 s[3..6]s[3..6] 重叠、s[3..6]s[3..6] 与 s[5..8]s[5..8] 重叠,而 s[1..4]s[1..4] 与 s[5..8]s[5..8] 不交——所以既能单独取任何一个,也能同时取两侧这两个。 右半边的箭头是转移中唯一会带来新分支的那一项 dp[i]+=dp[i−m]dp[i] \mathrel{+}= dp[i-m] (另一项 dp[i−1]dp[i-1] 只把前一格复制过来):匹配结束于 44 时从 dp[0]dp[0] 取一项、 结束于 66 时从 dp[2]dp[2] 取、结束于 88 时从 dp[4]dp[4] 取。起点下标恰好比结束位置小 mm, 说明“前面那一段允许再取深意”与“末段这段取深意”之间的重叠约束已经由下标差自动截断: dp[4]=2dp[4] = 2 被加上去时,它自己内部的那两条链条(全原意、只有 s[1..4]s[1..4] 取深意)都合法。