Luogu2679
/*
思路清晰:
1.状态
2.转移方程:哪些状态相互影响/记忆化搜索思想
3.循环顺序
4.优化
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
const int MAXN=1005;
const int MAXM=205;
char a[MAXN],b[MAXM];
LL dp[2][MAXM][MAXM][2];
int n,m,num,ans;
int main(){
scanf("%d%d%d",&n,&m,&num);
scanf("%s%s",a+1,b+1);
dp[0][0][0][0]=dp[1][0][0][0]=1;//状态最重要
for(int i=1;i<=n;i++){
int now=i&1;//应该先得一些分再去想优化
for(int j=1;j<=m;j++)
for(int k=1;k<=num;k++){//根据dp方程反推循环顺序
dp[now][j][k][0]=(dp[now^1][j][k][0]+dp[now^1][j][k][1])%mod;
if(a[i]==b[j])
dp[now][j][k][1]=(dp[now^1][j-1][k-1][0]+dp[now^1][j-1][k-1][1]+dp[now^1][j-1][k][1])%mod;
// 单独成串,不相连 单独成串,相连 接上一个串
else
dp[now][j][k][1]=0;
}
}
printf("%lld\n",(dp[n&1][m][num][0]+dp[n&1][m][num][1])%mod);
}