题解

题目类型：动态规划（滚动数组）
核心目标：给定字符串 a（长 n）与 b（长 m），统计恰好 k 段不相交的公共子串的方案数，结果对 1e9+7 取模。

“公共子串的段数”指把匹配的相同字符连续段当作一个块（block），要求总块数恰为 k。每个块在 a 和 b 中都是连续的，且各块互不重叠。

一、状态设计

使用两类 DP 状态（对 i 维度用滚动实现，代码中只显式开 j,t）：

• F1[j][t]：在处理到 a 的当前前缀、b 的前 j 个字符，且当前不处于匹配块（上一个字符不与 b[j] 对齐成块末尾）的方案数，块数为 t。
• F2[j][t]：在处理到 a 的当前前缀、b 的前 j 个字符，且当前处于匹配块末尾（即以 a[i]、b[j] 结尾的匹配块存在）的方案数，块数为 t。

初始化：

• F1[0][0] = 1（空前缀、0 段的唯一方式）
• 其余为 0。

遍历顺序：

• 外层 i = 1..n；
• 中层 j = m..1 递减（避免一轮内重复使用同一层更新后的值）；
• 内层 t = k..1 递减（同理）。

二、状态转移

1. “不在块中”的累积

在进入本轮 i 时，上一轮（i-1）的 F1[j][t] 与 F2[j][t] 都可以“什么也不做”地带到当前层，
因此先把旧值加到新的 F1[j][t]：

int p1 = F1[j][t], p2 = F2[j][t];
F1[j][t] = (p1 + p2) % MOD;

这一步相当于 dp1[i][j][t] = dp1[i-1][j][t] + dp2[i-1][j][t] 的滚动实现。

2. “在块中”的转移（当 a[i-1] == b[j-1]）

若 a[i] 与 b[j]（注意代码下标偏移）字符相同，可以使 F2[j][t] 来自三种情况：

• 开启新块：此前不在块，且块数加一
  F1[j-1][t-1]
• 延长当前块：此前就在块中
  F2[j-1][t]
• “接续开新块”：此前在块末尾并结束，再紧接着以当前字符开一块（等价于把上一块和当前这一位连起来形成更长的块，常见写法中会与开启/延长拆分处理；本代码采取合并写法）
  F2[j-1][t-1]

合并为：

F2[j][t] = (F1[j-1][t-1] + F2[j-1][t] + F2[j-1][t-1]) % MOD;

若字符不相同，则本位不能作为块末尾：

F2[j][t] = 0;

三、答案

遍历完 i=1..n 后，恰好 k 段的方案既可能以“不在块中”结束，也可能以“在块中”结束，
因此输出：

(F1[m][k] + F2[m][k]) % MOD

四、正确性直观理解

• F2 专门统计“以当前位置为块末尾”的方案，便于处理连续性（延长）与块数的+1（开启新块）。
• F1 则承接“当前不处于块中”的所有方案（既包括始终不匹配的选择，也包括之前在块中但现已结束的选择）。
• 递减循环保证一次 i 的更新只用到上一层 i-1 的值，等价于三维 DP 的滚动数组优化。

五、复杂度

• 时间复杂度：O(n * m * k)
• 空间复杂度：O(m * k)（对 i 维滚动）

六、实现（与题给代码一致）

#include<iostream>
#include<string>
using namespace std;
string a, b;
int n, m, k;
int main()
{
	cin >> n >> m >> k >> a >> b;
	int F1[m + 1][k + 1] = {}, F2[m + 1][k + 1] = {}; 
	F1[0][0] = 1;
	for (int i = 1;i <= n;i++)
	{
		for (int j = m;j >= 1;j--)
		{
			for (int t = k;t >= 1;t--)
			{
				int p1 = F1[j][t], p2 = F2[j][t];
				F1[j][t] = (p1 + p2) % 1000000007;
				if (a[i - 1] == b[j - 1])
				{
					F2[j][t] = ((F1[j - 1][t - 1] + F2[j - 1][t]) % 1000000007 + F2[j - 1][t - 1]) % 1000000007;
				}
				else
				{
					F2[j][t] = 0;
				}
			}
		}
	}
	cout << (F1[m][k] + F2[m][k]) % 1000000007 << endl;
}