记录编号	450630	评测结果	TTTTTTTTTT
题目名称	[NOIP 2015]子串	最终得分	0
用户昵称	+1s	是否通过	未通过
代码语言	C++	运行时间	10.017 s
提交时间	2017-09-16 16:52:03	内存使用	0.23 MiB

#include<cstdio>
int n,m,k;
char A[1010],B[222];
int dp(int i,int j,int l,int fl)//i-n   j-m   l-k
{
	if(A[i]=='\0'||B[j]=='\0')return 0;
	if(i==n&&j==m&&l==k)return 1;
	int tp=0;
	if(fl==1)
	if(A[i]==B[j])return dp(i+1,j+1,l+1,0)+dp(i+1,j+1,l,1)+dp(i+1,j+1,l+1,1);
	else return 0;
	else return dp(i+1,j,l,0)+dp(i+1,j,l,1);
}
int main()
{
	freopen("2015substring.in","r",stdin);
	freopen("2015substring.out","w",stdout);
	scanf("%d %d %d",&n,&m,&k);
	scanf("%s\n%s",A,B);
	printf("%d",(dp(0,0,0,0)%1000000007+dp(0,0,0,1)%1000000007)%1000000007);
	return 0;
}