AcWing 520. 子串(线性dp+前缀和优化时间+去一维优化空间)(有点难想)
原题链接
中等
作者:
逸误
,
2024-04-02 21:24:10
,
所有人可见
,
阅读 7
//先考虑如何dp,再考虑优化
//状态表示:f[i][j][k]:考虑A中前i个字母,拼出了B中的j个字母,用了k个子串
//状态划分:如果不取第i个字母,f[i][j][k]=f[i-1][j][k]
//如果取第i个字母,设这次已经取了长度为t的子串,f[i][j][k]=f[i-t][j-t][k-1]+sum(f[i-t][j-t][k-1])
//如果每次求sum都往前数t位,时间复杂度O(n*m*m*k),不能接受
//sum的计算重复,因此可以用更新的前缀和存一下
//空间复杂度又会超限,注意到对于每个f[i][j][k],都之和i-1层有关,且都只会用更小的j,k去更新f数组,因此可以空间优化去掉第一维i
//更新只用到更小的j,k,因此遍历时j,k要从大到小更新!
#include <iostream>
using namespace std;
const int N = 1005, M = 205, MOD = 1e9+7;
int n,m,K;
char a[N],b[M];
int sum[M][M];//前缀和数组,一个优化
int f[M][M];
int main()
{
cin>>n>>m>>K;
scanf("%s%s",a+1,b+1);
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=m;j;j--)
for(int k=K;k;k--)
{
if(a[i]==b[j])
sum[j][k]=(sum[j-1][k]+f[j-1][k-1])%MOD;
else
sum[j][k]=0;
f[j][k]=(sum[j][k]+f[j][k])%MOD;
}
cout<<f[m][K]<<endl;
return 0;
}