NOIP2015提高组--子串

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>

const int MAXN = 1000;
const int MAXM = 200;
const int MAXK = 200;
const int MOD = 1e9 + 7;

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);

    static char a[MAXN + 1], b[MAXM + 1];
    scanf("%s\n%s", a, b);

    static int f[2][MAXM + 1][MAXK + 1], g[2][MAXM + 1][MAXK + 1];
    g[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        const int curr = i % 2, prev = !curr;
        memset(f[curr], 0, sizeof(f[curr]));
        memset(g[curr], 0, sizeof(g[curr]));

        g[curr][0][0] = f[curr][0][0] = 1;
        for (int j = 1; j <= m; j++) {
            for (int t = 1; t <= std::min(j, k); t++) {
                if (a[i - 1] == b[j - 1]) {
                    f[curr][j][t] = (f[prev][j - 1][t] + g[prev][j - 1][t - 1]) % MOD;
                    g[curr][j][t] = (g[prev][j][t] + f[curr][j][t]) % MOD;
#ifdef DBG
                    printf("g[%d][%d][%d] = %d\n", i, j, t, g[curr][j][t]);
                    printf("f[%d][%d][%d] = %d\n", i, j, t, f[curr][j][t]);
#endif
                } else {
                    f[curr][j][t] = 0;
                    g[curr][j][t] = g[prev][j][t];
                }
            }
        }
    }

    printf("%d\n", g[n % 2][m][k]);

    return 0;
}