DP

设f[i][j[[k][0]表示A的前i个字符匹配B的前j个字符，划分成k段，且当前A串这个字符不取的情况下的方案数。

f[i][j][k][1]则表示A的前i个字符匹配B的前j个字符，划分成k段，且当前A串这个字符取的情况下的方案数。

容易得出，$f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]$，即从第i-1个状态直接转移过来。

$f[i][j][k][1]=f[i-1][j-1][k-1][0]+f[i-1][j-1][k-1][1]+f[i-1][j-1][k][1](当a[i]=b[j]时)$，分别表示前一个不取当前独成一个子串的情况，前一个取当前独成一个子串的情况和前一个取当前和前一个成同一个子串的情况。

边界$f[i][0][0][0]=1$。

最后答案为$f[n][m][k][0]+f[n][m][k][1]$。

四维数组开不下怎么办？观察状态转移方程可以发现，i的状态总是从i-1转移过来，与其他状态无关。故我们滚动第一维即可。

时间复杂度$O(nmk)$。

AC代码

#include<iostream>
#include<cstring>
#define ll long long
#define oo 1000000007
using namespace std;
ll f[2][202][202][2];
int n,m,K;
char a[1050],b[202];
int main(){
	memset(f,0,sizeof f);
	ios::sync_with_stdio(false);
	cin>>n>>m>>K>>(a+1)>>(b+1);
	f[0][0][0][0]=1;
	for(int i=1;i<=n;++i){
		int c=i&1;
		memset(f[c],0,sizeof f[c]);
		f[c][0][0][0]=1;
		for(int j=1;j<=m&&j<=i;++j){
			for(int k=1;k<=K&&k<=j;++k){
				f[c][j][k][0]=(f[c^1][j][k][0]+f[c^1][j][k][1])%oo;
				if(a[i]==b[j])
				f[c][j][k][1]=(f[c^1][j-1][k-1][1]+f[c^1][j-1][k-1][0]+f[c^1][j-1][k][1])%oo;
			}
		}
	}
	cout<<(f[n&1][m][K][0]+f[n&1][m][K][1])%oo<<endl;
	return 0;
}