$1 \le n \le 1000, 1 \le m \le 200, 1 \le k \le m$

我们发现 $A$ 的 $k$ 个子串拼接的 $S$，且 $S = B$ 的方案数。

我们定义这样的方案，我们发现这个子串的拼接方式是这样的：

1. 直接接到上次的子串后面

2. 单开一个新的子串

我们定义这样的状态，$f[i][j][k]$ 表示必须选择 $i$ 这个点，已经选择出来了 $k$ 个子串，能与 $B$ 的前 $j$ 个字符相匹配，定义 $g[i][j][k]$ 表示选或不选 $i$ 这个位置，剩下和 $f$ 的定义一样的方案数。

那么我们的转移是这样的：

- 当 $A_i = B_j$ 的时候

 那么 $f[i][j][k] = (f[i - 1][j - 1][k] + g[i - 1][j - 1][k - 1])$，这个东西就是，要么你拼接在后面，要么你单开一个，造成新的 $k$ 的贡献。我们的 $g[i][j][k] = (g[i][j][k] + f[i - 1][j][k])$，这个东西就是你不选 $i$ 的和上一次的。

- 当 $A_i \ne B_j$ 的时候

 那么我们的 $f[i][j][k] = 0$，我们的 $g[i][j][k] = g[i- 1][j][k]$。

但是我发现此时的空间超限，我们发现每次的 $i$ 只从 $i - 1$ 转移，于是我们很愉快的滚动数组优化一下即可。或者倒序枚举。