题解 | #[NOIP2015]子串#

#include <iostream>
#include <cstring>
using namespace std;

const int MOD = 1000000007;

int main() {
    int n, m, K;
    cin >> n >> m >> K;
    string A, B;
    cin >> A >> B;
    // 调整字符串索引从1开始，方便处理
    A = " " + A;
    B = " " + B;

    // dp[j][k] 表示当前处理A的前i个字符时，匹配B的前j个字符，并分成k个子串的方案数
    // 由于状态转移只依赖于上一层(i-1)，因此可以使用滚动数组优化空间
    int f[205][205] = {0}; // f[j][k]：A的第i个字符被使用时，形成k个子串的方案数
    int g[205][205] = {0}; // g[j][k]：A的前i个字符匹配B的前j个字符，形成k个子串的总方案数（包含使用和不使用A[i]）

    // 初始化：两个空串匹配0个子串，方案数为1
    f[0][0] = 1;
    g[0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        // 注意：j需要从大到小遍历，因为我们需要用到上一层(j-1)的状态
        // 如果从小到大遍历，会用到本层已更新的状态，导致错误（类似于01背包的优化）
        for (int j = m; j >= 1; --j) {
            for (int k = 1; k <= K; ++k) {
                if (A[i] == B[j]) {
                    // 如果A[i]等于B[j]，那么A[i]可以被使用
                    // 方案来源有两种：
                    // 1. 将A[i]接在上一段子串的后面：f[j-1][k]
                    // 2. 用A[i]新开一段子串：g[j-1][k-1]
                    f[j][k] = (f[j-1][k] + g[j-1][k-1]) % MOD;
                } else {
                    // 如果A[i]不等于B[j]，则A[i]不能被使用来匹配B[j]
                    f[j][k] = 0;
                }
                // 总方案数g[j][k] = 使用A[i]的方案数 + 不使用A[i]的方案数
                // 不使用A[i]的方案数就是上一轮i-1时匹配到j,k的总方案数，即g_old[j][k]
                // 由于我们使用滚动数组，需要在更新g[j][k]前记录旧值，这里通过计算顺序实现：
                // 我们先计算了新的f[j][k]，然后新的g[j][k] = (g[j][k] + f[j][k]) % MOD
                // 此时的g[j][k]在加上f[j][k]前，保存的还是上一轮(i-1)的总方案数
                g[j][k] = (g[j][k] + f[j][k]) % MOD;
            }
        }
    }

    // 最终答案：用A的前n个字符，匹配B的前m个字符，分成K个子串的总方案数
    cout << g[m][K] << endl;
    return 0;
}