AcWing 520. 子串
原题链接
中等
作者:
Air1222
,
2024-04-06 16:46:17
,
所有人可见
,
阅读 4
//菜鸡只配写暴力
//f[i][j][k]:从a中前i个字符中选择,共选k段,与b的前j个字母匹配
#include <iostream>
using namespace std;
const int N = 1010,M=210,MOD = 1000000007;
char a[N],b[N];
int f[N][M][M];
int main()
{
int n,m,s;
cin>>n>>m>>s;
cin>>a+1>>b+1;
for(int i=0;i<=n;i++) f[i][0][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=min(i,m);j++)
for(int k=1;k<=min(s,j);k++)
{
f[i][j][k]=f[i-1][j][k]%MOD;//不选
for(int x=1;x<=j;x++)
{
if(a[i-x+1]==b[j-x+1])
//选,每一次可以添加连续一段相等的字符串
//因此当前相等的一端可以拆分成不同的两端,每一个都可以转移
f[i][j][k]=(f[i][j][k]+f[i-x][j-x][k-1])%MOD;
else break;
}
}
cout<<f[n][m][s]%MOD;
return 0;
}