题目

题解：

f[j][k]表示：一定取到a[i]时，在B的前j位中取了k个子串的方法数
g[j][k]表示：a的前i位，B的前j位取了k个子串的方法数（对是否取到a[i]没有要求）
f[i][j][k]+=f[i-1][j-1][k]（把这位接在原来的后面）+g[i-1][j-1][k-1]（单独作为一个子串）
g[i][j][k]+=f[i-1][j][k]+g[i-1][j][k]
可用类似背包的方法省略一维

标程：

#include<bits/stdc++.h>
using namespace std;
const int M=1e9+7;
int n,m,K,f[202][202],g[202][202],i,j,k;
char s1[1002],s2[202];
int main(){
    scanf("%d%d%d%s%s",&n,&m,&K,s1,s2);
    f[0][0]=g[0][0]=1;
    for (i=1;i<=n;i++)
        for (j=m;j;j--)
            for (k=1;k<=K;k++){
                if (s1[i-1]!=s2[j-1]){
                    f[j][k]=0;
                    continue;
                }
                f[j][k]=(f[j-1][k]+g[j-1][k-1])%M;
                g[j][k]=(f[j][k]+g[j][k])%M;
            }
    printf("%d",g[m][K]);
}