P2679 子串
题意
有两个仅包含小写英文字母的字符串 A和 B。现在要从字符串 A中取出 k个互不重叠的非空子串。
然后把这 k 个子串按照其在字符串 A中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 B相等。
分析
看到这种字符串拼接的题目,先试试数据范围n*nk的范围能不能过,因为这是dp的复杂度,发现时间足够,就开始思考如何转移。
dp的定义:d$[i][j][k] $表示A中前i个和B中前j个全部匹配成功,同时已经取出k个字串的状态,记录一下方案数。
分成两个部分:
- A[i]和B[j]不同,那么他的方案数=d$[i-1][j-1][k]$
- A[i]和B[j]相同,假设p,满足0-(p-1)中A[i-p+1]==b[j-p+1],同时A[i-p]!=B[i-p]:翻译过来就是找到第一个不能取一次子串能够和B中的对应相等的情况
- 也就是$d[i-1][j][k]+d[i-1][j-1][k-1]+d[i-2][j-2][k-1].....d[i-p+1][j-p+1][k-1]$.
- 设一个sum$[j][k]$数组来优化这个过程,表示前j个中使用k次的前缀和。当碰到一个不相等的就置为0,否则就加上$d[i-1][j-1][k-1]$.
- 因为sum$[j][k]$=sum$[j-1][k]$然后多了一项,是因为多了一个公共的长度,也即是$d[i-1][j-1][k-1]$.
Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=300,mod=1000000007;
int d[N][N];
int sum[N][N];
char a[1200];
char b[N];
signed main()
{
int n,m,k;cin>>n>>m>>k;
cin>>a+1;
cin>>b+1;
d[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=1;j--)
{
for(int z=k;z>=1;z--)
{
if(a[i]!=b[j])
{
sum[j][z]=0;
d[j][z]=(d[j][z]+sum[j][z])%mod;
}
else
{
sum[j][z]=sum[j-1][z]+d[j-1][z-1];
d[j][z]=(d[j][z]+sum[j][z])%mod;
}
}
}
}
cout<<d[m][k]<<endl;
}