- 子串
- 2025-03-21 18:35:31 @
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=1000+5,M=200+5;
const int mod=1e9+7;
char s1[N],s2[M];
int n,m,K;
int dp[2][N][M],sum[2][N][M];
//dp[i][j][k]=Σdp[i-1][j']k-1 +dp[i-1][j-1][k]
int main(){
scanf("%d%d%d%s%s",&n,&m,&K,s1+1,s2+1);
memset(dp,0,sizeof dp);
memset(sum,0,sizeof sum);
int I=0,J=1;
for (int i=1;i<=n;i++){
if (s2[1]==s1[i])
dp[0][i][1]=1;
sum[0][i][1]=sum[0][i-1][1]+dp[0][i][1];
}
for (int i=2;i<=m;i++,I^=1,J^=1){
memset(dp[J],0,sizeof dp[J]);
memset(sum[J],0,sizeof sum[J]);
for (int j=1;j<=n;j++){
if (s2[i]!=s1[j])
continue;
for (int k=1;k<=K;k++)
if (j>=2)
dp[J][j][k]=(sum[I][j-1][k-1]+dp[I][j-1][k])%mod;
else
dp[J][j][k]=dp[I][j-1][k];
}
for (int k=1;k<=K;k++)
for (int j=1;j<=n;j++)
sum[J][j][k]=(sum[J][j-1][k]+dp[J][j][k])%mod;
}
return 0;
}
拿去用吧,第一个!!!!!!!!!
@元昊选
0 条评论
信息
- ID
- 1413
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 4
- 已通过
- 2
- 通过率
- 50%
- 上传者