因为该题需要求解方案数，因此我们不能用计数题的常用方法，即用递推来解决，类似于动态规划的思想。
我们用(dp[i][j][h][o])表示第一个串枚举到了(i)，第二个串枚举到了(j)，(A)中取了(h)串，(o)表示选不选当前第i位的方案数。
可以得出以下的状态转移：
如果此位不选择的话
(dp[i][j][h][0]=dp[i-1][j][h][0]+dp[i-1][j][h][1])，此位不选则用加法原理选之前一位选择的和。
如果此位选择的话：
如果(a[i])和(b[j])不相等的话选择该位不能产生一个满足条件的子串。
如果相等的话，子串个数增加和不增加的情况都需要考虑，子串个数不增加的话，则(i-1)必须选，而选了(i)之后子串个数增加的话，(i-1)可选可不选。注意此时第二个串应该加上枚举到(j-1)的方案。
然后i的转移只跟i-1有关，因此考虑空间优化
#include <bits/stdc++.h>
#define N 1001001
#define mod 1000000007
using namespace std;
int n, m, k, dp[2][1001][1001][2];
char a[N], b[N];
void init()
{
scanf("%d%d%d", &n, &m, &k);
scanf("%s%s", a + 1, b + 1);
dp[0][0][0][0] = dp[1][0][0][0] = 1;
}
int add(int a, int b) {return (a + b) % mod;}
int main()
{
init();
for (int i = 1, now = 1; i <= n; i++, now ^= 1)
for (int j = 1; j <= m; j++)
for (int h = 1; h <= k; h++)
{
dp[now][j][h][0] = (dp[now ^ 1][j][h][1] + dp[now ^ 1][j][h][0]) % mod;//上一位
if (a[i] == b[j])
{
dp[now][j][h][1] = 0;
dp[now][j][h][1] = (dp[now][j][h][1] + dp[now ^ 1][j - 1][h][1]) % mod;
dp[now][j][h][1] = (dp[now][j][h][1] + dp[now ^ 1][j - 1][h - 1][1]) % mod;
dp[now][j][h][1] = (dp[now][j][h][1] + dp[now ^ 1][j - 1][h - 1][0]) % mod;
}
else dp[now][j][h][1] = 0;
}
printf("%d", (dp[n & 1][m][k][0] + dp[n & 1][m][k][1])% mod);//第一位判断是否是奇数或偶数，最后一位判断是否相等。
}