// Problem: P2679 [NOIP2015 提高组] 子串
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2679
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010, M = 210, mod = 1e9 + 7;

int n, m, K;
char a[N], b[M];
int f[N][M][M];

int main()
{
	scanf("%d%d%d", &n, &m, &K);
	scanf("%s%s", a + 1, b + 1);
	
	f[0][0][0] = 1;
	for(int i = 1; i <= n; i ++ )
		for(int j = 1; j <= m; j ++ )
			for(int k = 1; k <= K; k ++ )
			{
				f[i][j][k] = f[i - 1][j][k];
				for(int len = 1; len <= i && len <= j; len ++ )
				{
					if(a[i - len + 1] != b[j - len + 1]) break;
					f[i][j][k] = (f[i][j][k] + f[i - len][j - len][k - 1]) % mod;
				}
			}
	
	int res = 0;
	for(int i = 1; i <= n; i ++ ) res = (res + f[i][m][K]) % mod;
	
	printf("%d\n", res);
	
	return 0;
}

数据：

.in:
6 3 2
aabaab
aab

.out:
10

.ans:
7

真心感谢