• 有两个仅包含小写英文字母的字符串A和B
  • 现在要从字符串A中取出k个互不重叠的非空子串，然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字符串
  • 求使得新串与B串相同的方案数
  • 子串取出的位置不同，认为是不同的方案。

题解

设f(i,j,t)f(i,j,t)表示使用从串A中前ii位取出的tt个子串匹配串B前jj位（必选AiA_i）的方案数，g(i,j,t)g(i,j,t)表示使用串A中前ii位取出的tt个子串匹配串B的前jj位（不必选AiA_i）的方案数。

计算f(i,j,t)f(i,j,t)时，考虑AiA_i作为前一个子串的最后一位的方案数，即f(i−1,j−1,t)f(i-1,j-1,t)，与单独作为一个子串的方案数，即g(i−1,j−1,t−1)g(i-1,j-1,t-1)，则对于f(i,j,t)f(i,j,t)，有：

f(i,j,t)={f(i−1,j−1,t)+g(i−1,j−1,t−1)Ai=Bj0Ai≠Bj f(i,j,t)= \begin{cases} f(i-1,j-1,t)+g(i-1,j-1,t-1) & A_i = B_j \\ 0 & A_i\neq B_j \end{cases}

对于g(i,j,t)g(i,j,t)，则有：

g(i,j,t)={g(i−1,j,t)+f(i,j,t)Ai=Bjg(i−1,j,t)Ai≠Bj g(i,j,t)= \begin{cases} g(i-1,j,t)+f(i,j,t) & A_i=B_j \\ g(i-1,j,t) & A_i\neq B_j \end{cases}

需要滚动数组优化

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1000;
const int MAXM = 200;
const int MAXK = 200;
const int MOD = 1e9 + 7;
int main () {
    static int f[2][MAXN + 1][MAXM + 1], g[2][MAXN + 1][MAXM + 1];
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    static char A[MAXN], B[MAXM];
    scanf("%s\n%s", A, B);
    g[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        const int cur = i % 2, pre = !cur;
        memset(f[cur], 0, sizeof(f[cur]));
        memset(g[cur], 0, sizeof(g[cur]));
        g[cur][0][0] = f[cur][0][0] = 1;
        for (int j = 1; j <= m; j++) {
            for (int t = 1; t <= min(j, k); t++) {
                if (A[i - 1] == B[j - 1]) {
                    f[cur][j][t] = ((f[pre][j - 1][t] % MOD) + (g[pre][j - 1][t - 1] % MOD)) % MOD;
                    g[cur][j][t] = ((g[pre][j][t] % MOD) + (f[cur][j][t] % MOD)) % MOD;
                } else {
                    f[cur][j][t] = 0;
                    g[cur][j][t] = g[pre][j][t];
                }
            }
        }
    }
    printf("%d\n", g[n % 2][m][k]);
    return 0;
}