P2679 子串
对应章节：五、数据结构与算法 → （十三） 动态规划（DP）基础。
（一） 任务与输出目标
从 A 中取 k 个按顺序互不重叠的非空子串，连接成 B，统计位置与分段方案。
（二） 建模与推导
只记录已匹配长度 j 与段数 t 还不够：读入当前 A 字符时，要区分前一位置是否正处在所选片段末尾，才能决定是否延长。定义 F(i,j,t) 为 A 前 i 个字符取 t 段并连接成 B 前 j 个字符的总方案数；E(i,j,t) 为其中最后一段恰好结束在 A 的第 i 个字符的方案数。
A[i-1] 与 B[j-1] 不同，则当前位置不能成为所选末尾，E=0。相同时，按最后一段的长度分类：它只有一字符，删去这段后来自 F(i-1,j-1,t-1)；它更长，删去最后一字符后仍有 t 段且最后一段结束于 i-1，来自 E(i-1,j-1,t)。两类分别是新开一段与延长现有段，接回字符能唯一恢复，故两项相加。相邻子串也可以是不同段，新开时使用 F，所以这些不同切分会分别计数。
总方案分为不用 A 第 i 个字符的 F(i-1,j,t)，与用它作末尾的 E(i,j,t)，于是 F 两项相加。初始 F(i,0,0)=1、其他没有字符可取的状态为 0；按 i 递增，用两层数组保留前一位置的 F、E。每个结果对 10^9+7 取模，答案为 F(n,m,k)。
（三） 手算与过程
A=aaa、B=aaa、k=2：取全部位置，切为 a|aa 或 aa|a，共 2。E 的“延长”和“新开”恰好区分这两个最后决策。
（四） 带注释实现
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve() {
int n, m, k;
string a, b;
cin >> n >> m >> k >> a >> b;
const int mod = 1000000007;
vector<vector<int>> f(m + 1, vector<int>(k + 1, 0)), e = f;
f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
vector<vector<int>> nf(m + 1, vector<int>(k + 1, 0)), ne = nf;
nf[0][0] = 1;
for (int j = 1; j <= m; ++j)
for (int t = 1; t <= k; ++t) {
if (a[i - 1] == b[j - 1])
ne[j][t] = (e[j - 1][t] + f[j - 1][t - 1]) % mod; // 延长，或新开一段。
nf[j][t] = (f[j][t] + ne[j][t]) % mod; // 不选当前位置，或让它成为末尾。
}
f.swap(nf);
e.swap(ne); // 两种前驱都必须来自前一个 i。
}
cout << f[m][k] << '\n';
}
signed main() {
ios::sync_with_stdio(false); // 关闭同步，使用 cin 与 cout 完成输入输出。
cin.tie(0), cout.tie(0);
int T = 1; // 本题读入一组数据。
// cin >> T; // 题目给出测试组数时开启，并在 solve 中处理一组。
while (T--)
solve();
}（五） 复杂度
时间 \(O(nmk)\)，滚动数组空间 \(O(mk)\)。