子串

史上最简短的一篇博客，毕竟看题解ac心疼我的kmp
/*

f[i][j][k][0/1]表示A的前i个，B的前j个，用到了k个子串，当前字符选或者不选。

所以f[0][0][0][0]的方案数为1

如果当前方案不选，那么就是前一个选和不选的方案转移

如果当前方案选，那么就是前一个方案前一个字母选，新开一个子串，前一个方案不选，继承上一子串，前一个方案选，继承上一子串

*/

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 1005, M = 205, mod = 1e9 + 7;

int n, m, K, f[2][M][M][2];

char a[N], b[M];

int main() {

    int i, j, k;

    scanf("%d%d%d",&n,&m,&K);

    scanf("%s",a+1);

    scanf("%s",b+1);

    f[0][0][0][0] = 1;

    for (i = 1; i <= n; i++) {

        int opt = i&1; f[opt][0][0][0] = 1;

        for (j = 1; j <= min(i, m); j++)

        	for (k = 1; k <= min(j, K); k++) {

            	f[opt][j][k][0] = f[opt][j][k][1] = 0;

            	f[opt][j][k][0] = (f[opt ^1][j][k][0] + f[opt^1][j][k][1]) % mod;

            	if (a[i] == b[j]) {

            	    f[opt][j][k][1]=(f[opt^1][j-1][k][1]+f[opt^1][j-1][k-1][0])%mod;

            	    (f[opt][j][k][1]+=f[opt^1][j-1][k-1][1])%=mod;

            }

        }

    }

    printf("%d\n",(f[n&1][m][K][0]+f[n&1][m][K][1])%mod);

    return 0;

}
巴特西

luogu 2679 子串

子串

最新文章

热门文章
