P2679 子串

P2679 子串

题意:

给出两个仅含小写字母的字符串 \(A\) 和 \(B\) 要求从 \(A\) 中取出 \(k\) 个互不重叠的非空子串，然后把这 \(k\) 个子串按照其在字符串 \(A\) 中的顺序依次连接起来形成新的字符串。

求有多少种方案可以使得这个新字符串和字符串 \(B\) 相等？

思路:

定义 \(f[i][j][k]\) ，为遍历到第 \(i\) 个字符，取出了 \(k\) 个子串，这 \(k\) 个子串，匹配到 \(B\) 字符串的第 \(j\) 个字符，划分为匹配的时候当前是成为一个新的子串，还是和之前的合并。但是合并的时候，必须先前面也是匹配的，所以考虑再加一个维度，标记第 \(i\) 个点是否选入。定义 \(f[i][j][k][h]\) ：为遍历到 \(A\) 串的第 \(i\) 个位置使用了 \(k\) 个子串匹配了 \(B\) 的前 \(j\) 个字符，第 \(i\) 个位置选或不选的方案数。

划分依据为 第 \(i\) 个选或者不选

• 当 \(a_i = b_j\) 时
  • 当前不选：\(f_{i,j,k,0} = f_{i - 1,j,k,0} + f_{i - 1,j,k,1}\)
  • 当前选：\(f_{i,j,k,1} = f_{i - 1,j - 1,k - 1,0} + f_{i - 1,j - 1,k - 1,1}\)
• 当 \(a_i \not = b_j\) 时
  • 不选情况同上
  • 没办法选，\(f_{i,j,k,1} = 0\)

发现空间太大了，然后观察公式，发现只需要用到 \(i - 1\) 所以可以滚动，注意这里因为更新 \(k\) 时会用到 \(i -1\) 的 \(k\) 所以不能自我滚动。

实现:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5, M = 205, mod = 1e9 + 7;
char a[N], b[M];
ll f[2][M][M][2];
int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    scanf("%s", a + 1);
    scanf("%s", b + 1);
    f[1][0][0][0] = f[0][0][0][0] = 1;
    // 遍历到 a 的哪个位置
    for (int i = 1; i <= n; i++)
    { // 匹配到 b 的哪个位置
        for (int j = 1; j <= m; j++)
            // 分成了几个子串
            for (int h = 1; h <= k; h++)
            {
                // 当前不匹配
                f[i & 1][j][h][0] = (f[(i & 1) ^ 1][j][h][0] + f[(i & 1) ^ 1][j][h][1]) % mod;

                // 当前匹配
                if (a[i] == b[j])
                {
                    // 另为一段
                    f[i & 1][j][h][1] = (f[(i & 1) ^ 1][j - 1][h - 1][0] + f[(i & 1) ^ 1][j - 1][h - 1][1]) % mod;
                    // 和之前的合并为一段
                    f[i & 1][j][h][1] = (f[i & 1][j][h][1] + f[(i & 1) ^ 1][j - 1][h][1]) % mod;
                }
                else
                    f[i & 1][j][h][1] = 0;
            }
    }

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

    return 0;
}