形式化题目

给定字符串 $A$（长度 $n$）与 $B$（长度 $m$），以及正整数 $k$。从 $A$ 中取出 $k$ 个互不重叠的非空子串，按它们在 $A$ 中出现的顺序依次连接，问连接结果恰好等于 $B$ 的方案数；子串取自不同位置算不同方案。答案对 $1000000007$ 取模。

等价地，选 $2k$ 个边界：

由于每个子串非空、不重叠且按序使用，被选中的字符保持它们在 $A$ 中的相对顺序，拼接结果的第 $j$ 位必然来自"第 $j$ 个被选中的 $A$ 字符"——按序拼接就是与 $B$ 逐位对照，这是后面一切推导的起点。

样例（$A=$ aabaab，$B=$ aab）的三个答案：

• $k = 1$：一整段必须等于 aab，它在 aabaab 中出现于 $[1,3]$、$[4,6]$，共 2 种。
• $k = 2$：$B$ 只能拆成 a+ab 或 aa+b。a+ab：a 取自位置 $\{1,2,4,5\}$，ab 出现在 $(2,3)$、$(5,6)$，前段须整体位于后段左侧，得 $1 + 3 = 4$ 种；aa+b：aa 出现在 $(1,2)$、$(4,5)$，b 在 $\{3,6\}$，得 $2 + 1 = 3$ 种。合计 7 种。
• $k = 3$：只能拆 a+a+b。前两个 a 的位置对共 6 种，$(1,2)$ 可配 $b \in \{3,6\}$，其余 5 对只能配 $b = 6$，共 $2 + 5 =$ 7 种。

正解

思路

1. 朴素做法与瓶颈

最朴素的做法是枚举 $2k$ 个边界 $(l_1, r_1, \dots, l_k, r_k)$ 再拼串比较，方案数是 $\binom{n}{2k}$ 量级，$n = 1000$ 时完全不可行。可行的等价形态是按 $A$ 从左到右扫描的递推/记忆化搜索：每看到一个 $A$ 的字符有三种选择——不选它、把它接进当前段、让它开一个新段——同时维护已拼出 $B$ 的前几位和已用段数，状态数 $O(nmk)$。

但"只用一个 $f[i][j][p]$（$A$ 前 $i$ 字符、$B$ 前 $j$ 字符、$p$ 段）"无法转移：判断 $A[i]$ 能否接进当前段，要知道上一个被选中的字符是不是 $i-1$、它拼到了 $B$ 的哪一位，而这些信息没有被 $f$ 记录。瓶颈就在这里——必须补一个"最后一段右端点在哪"的状态，把"接段尾"和"开新段"两种来源拆开。

2. 状态定义

• $f[i][j][p]$：考虑 $A$ 的前 $i$ 个字符，能拼出 $B$ 的前 $j$ 个字符、共取 $p$ 段的方案数（$A[i]$ 用不用都可以）；
• $g[i][j][p]$：在 $f$ 的基础上，额外要求第 $p$ 段以 $A[i]$ 结尾（$A[i]$ 必被选中、且它匹配 $B[j]$）的方案数。只有 $A[i] = B[j]$ 时 $g[i][j][p]$ 才可能非零。

3. 转移与初始化

当 $A[i] = B[j]$ 时，右端点恰为 $i$ 的方案按"上一个字符 $A[i-1]$ 是否属于同一段"二分，互斥且穷尽：

• 接段尾：上一步 $A[i-1]$ 已匹配 $B[j-1]$ 且就在第 $p$ 段里，正是 $g[i-1][j-1][p]$ 的定义；
• 开新段：第 $p$ 段只含 $A[i]$，前 $i-1$ 个字符只需用 $p-1$ 段拼出 $B$ 的前 $j-1$ 位，即 $f[i-1][j-1][p-1]$；
• $A[i] \neq B[j]$ 时 $A[i]$ 不可能匹配 $B[j]$，$g[i][j][p] = 0$。

$f$ 按"$A[i]$ 是否被选中"二分：

初始化：$f[i][0][0] = 1$（空串用 0 段拼出，只有"什么都不取"），其余全 0；$g$ 初始全 0。注意 $p = 1$ 的"开新段"来源是 $f[i-1][j-1][0]$，它只在 $j = 1$ 时等于 1——这正是"新段从 $A[i]$ 起步、拼出 $B$ 的首位"。答案是 $f[n][m][k]$。

对 $i$ 归纳：$g$ 的两来源覆盖"右端点为 $i$"的全部方案、$f$ 的两项按"$A[i]$ 用没用"二分，转移不重不漏，初始化覆盖空串边界，故答案正确。

样例 $k = 1$ 时 $f[i][j][1]$ 的完整表格（viz_render.py 教学版 DP 复算，与 main.py 结果一致）：

行是 $A$ 前缀长度 $i$，列是 $B$ 前缀长度 $j$，格子是 $f[i][j][1]$（取 1 段拼出 $B$ 前 $j$ 位的方案数）。重点看第 1 列：$A$ 每出现一个 a 就 $+1$（如 $i = 4$ 时 $g[4][1][1]$ 由"开新段"来源 $f[3][0][0] = 1$ 得到，段 $[4,4]$ 拼出 $B[1]$）；再看格子 $(5, 2) = 2$：$f[4][2][1] = 1$（段 $[1,2]$）加上 $g[5][2][1] = g[4][1][1] + f[4][1][0] = 1 + 0$（段 $[4,4]$ 的尾部续上 $A[5]$ 得段 $[4,5]$，开新段来源此格为 0），正是"接段尾"与"沿用旧方案"两路之和。最终 $f[6][3][1] = 2$，与样例一致。

4. 滚动数组与更新顺序

状态数 $(n+1)(m+1)(k+1)$ 最大 $4 \times 10^7$，三维全开在 Python 里超内存也超时，做两步压缩：

• $g$ 滚两层：$g[i][\cdot][\cdot]$ 只依赖 $g[i-1][\cdot][\cdot]$ 与 $f[i-1][\cdot][\cdot]$，逐字符保留"上一个字符"和"当前字符"两层即可（代码中 g_prev / g_cur 交换）；
• $f$ 原地累加：$f[i][j][p] = f[i-1][j][p] + g[i][j][p]$ 对 $i$ 只增不减，一维数组原地更新；非匹配列 $g = 0$，$f$ 行保持不变（仍指向同一 list，无需整行复制）。

由此带出一个实现上必须回答的问题：同一轮内 $g[i][j]$ 要读 $f[i-1][j-1]$，而 $f$ 是原地累加的，怎么保证读到旧值？把匹配列从右往左更新——本轮只更新当前列 $j$，读的却是左邻 $j-1$，倒序使 $j-1$ 留在上一层。再预处理 cols_of（$B$ 中每个字符出现的列号），扫描 $A$ 时只访问可能匹配的列，实际工作量从 $n \cdot m \cdot k$ 降到"匹配对数 $\times\ k$"。取模利用"两加数都 $< \mathrm{MOD}$、和 $< 2\,\mathrm{MOD}$"，用减一次 MOD 代替逐元素取模。

（代码里下标 0-based：f[col][t] 对应 $f[i][\mathrm{col}][t+1]$，seg_one_start 即 $j = 1$ 时的 $f[\cdot][0][0]$，答案取 f[len(B)][k - 1]。）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); int n,m,k; if(!(cin>>n>>m>>k)) return 0; string A,B; cin>>A>>B; vector<vector<int> > cols(256); for(int i=0;i<m;i++) cols[(unsigned char)B[i]].push_back(i+1); vector<vector<int> > f(m+1, vector<int>(k)), gprev(m+1, vector<int>(k)); for(int idx=0;idx<n;idx++){unsigned char ch=A[idx]; vector<vector<int> > gcur(m+1, vector<int>(k)); vector<int> &vc=cols[ch]; for(int id=(int)vc.size()-1; id>=0; id--){int col=vc[id]; for(int t=0;t<k;t++){ll y = (t==0 ? (col==1?1:0) : f[col-1][t-1]); ll v = gprev[col-1][t] + y; if(v>=MOD) v-=MOD; int joined=v; ll nf=f[col][t]+joined; if(nf>=MOD) nf-=MOD; f[col][t]=nf; gcur[col][t]=joined;}} gprev.swap(gcur);} cout<<f[m][k-1]<<'\n'; return 0;}

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#!/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-02 12:05
# update_at: 2026-10-04 13:32

import sys

MOD = 1000000007


def count_plans(A: str, B: str, k: int) -> int:
    """从 A 中取 k 个互不重叠子串按序拼出 B 的方案数（对 MOD 取模）。

    f[j][t]：已扫描的 A 前缀能拼出 B[:j]、取 t+1 段的总方案数（A 当前字符用不用均可）；
    g[j][t]：在 f 的基础上额外要求最后一段以刚扫过的那个 A 字符匹配 B[j-1] 结尾。

    A[i] 与 B[j-1] 匹配时 g 才非零，转移恰有两种：接在当前段尾用 g[j-1][t]，
    让 A[i] 开新段用 f[j-1][t]（即凑 B[:j-1] 只用 t 段，新段从 A[i] 起步）。
    """
    # B 中每个字符出现的列号（1-based）：扫描 A 时只访问可能匹配的列
    cols_of: dict[str, list[int]] = {}
    for col, ch in enumerate(B, 1):
        cols_of.setdefault(ch, []).append(col)

    zero = [0] * k
    # f[0][t] 恒为 0：空串 B[:0] 取正段数不可能；第 0 列永远不更新
    f: list[list[int]] = [[0] * k for _ in range(len(B) + 1)]
    g_prev: list[list[int]] = [zero] * (len(B) + 1)  # 上一个 A 字符处的 g

    for ch in A:
        # 列号从右往左更新，读到的 f[col-1] 才会停留在上一个字符的那一层
        g_cur: list[list[int]] = [zero] * (len(B) + 1)
        for col in reversed(cols_of.get(ch, ())):
            seg_one_start = 1 if col == 1 else 0  # f[·][0][0]：0 段拼出空串恰有 1 种
            # 逐段位合并"接段尾 + 开新段"；两数都 < MOD，和减一次 MOD 即回 [0, MOD)
            joined = [
                v - MOD if (v := x + y) >= MOD else v
                for x, y in zip(g_prev[col - 1], [seg_one_start] + f[col - 1][:k - 1])
            ]
            f[col] = [v - MOD if (v := x + y) >= MOD else v for x, y in zip(f[col], joined)]
            g_cur[col] = joined
        g_prev = g_cur

    return f[len(B)][k - 1]


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n, m, k = int(next(data)), int(next(data)), int(next(data))  # 题面的 |A|、|B| 与段数，转移只依赖 k
    print(count_plans(next(data).decode(), next(data).decode(), k))


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：$O(n \cdot m \cdot k)$ 上限，与正解同阶；实现只在匹配列做转移，实际为"匹配对数 $\times\ k$"，最大单测（$n = 1000, m = 100, k = 89$，匹配对 99400）本地实测 0.635s。
• 空间复杂度：$O(m \cdot k)$：$f$ 一维 $(m+1) \times k$，$g$ 两层，非匹配列共享零数组；实测峰值约 17MB（含 Python 解释器），远低于 32MB。
• 实测：数据仓 10 组真实数据全部 PASS，最慢 0.678s；Python 满规模无 TLE/MLE 风险，若 $n, m, k$ 再放大一个量级则需注意。

总结

• "按序拼出 $B$"等价于与 $B$ 逐位对照，所以外层扫描 $A$：不重叠、有序都由扫描顺序天然保证。
• 单靠 $f[i][j][p]$ 不知道最后一段的右端点，补 $g[i][j][p]$（最后一段以 $A[i]$ 结尾）后，转移恰好是两路：接段尾用 $g[i-1][j-1][p]$、开新段用 $f[i-1][j-1][p-1]$。
• $g$ 滚两层、$f$ 原地累加、匹配列倒序更新、只访问匹配列——四件事把 $O(nmk)$ 三维表压成 $O(mk)$ 且在 Python 中跑进时限。

图示解析

这张图串起本题从朴素枚举到最终答案的主线：

1
2
3
4枚举 2k 个边界 -> 组合爆炸，不可行
`- 关键观察：按序拼接 = 与 B 逐位对照，外层扫 A 定序
   `- 补状态 g[i][j][p]：接段尾用 g，开新段用 f，两路合并
      `- g 滚两层 + f 原地累加 + 匹配列倒序 -> 答案 f[n][m][k]

先看每个节点记录的推理结论，再顺着 `- 分支检查它如何自然导出下一步：每一层都只解决了上一层留下的一个瓶颈。图中不含完整 DP 表与代码细节，具体格子的转移仍以正文表格为准。