记录编号	532273	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]子串	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.292 s
提交时间	2019-05-27 13:21:34	内存使用	13.99 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=207;
const int Mod=1e9+7;
int kk,l1,l2;
char s1[N<<4],s2[N];
int dp[N][N],g[N][N];//dp[i][j]表示匹配到s2第i位用了j个子串
//g[i][j]表示匹配到s2的第i位用j个子串所有的方案数 
int main()
{
	freopen("2015substring.in","r",stdin);
	freopen("2015substring.out","w",stdout);
	scanf("%d%d%d",&l1,&l2,&kk);
	scanf("%s%s",s1+1,s2+1);
	dp[0][0]=1;
	for (int i=1;i<=l1;i++)
		for (int j=l2;j;j--)
	 		for (int p=kk;p;p--)
	 			if (s1[i]!=s2[j]) {g[j][p]=0;continue;}
	 			else 
	 			{
	 				g[j][p]=(g[j-1][p]+dp[j-1][p-1])%Mod;
	 				dp[j][p]=(g[j][p]+dp[j][p])%Mod;
				}
	printf("%d",dp[l2][kk]);
	return 0; 
}