Codeforces Round #820 G. Cut Substrings 题解

这是一道很直接的 DP 题但难点在于知道从哪转移。首先我们找到 $t$ 在 $s$ 中的所有出现位置并记为 $pos$ 。定义 $f_i$ 为消除前 $i$ 次出现所需要的最小次数，且第 $i$ 个出现是完整消除的（这样可以避免数重），定义 $g_i$ 为所对应的不同方法的次数。

当考虑第 $i$ 个出现时，首先找到 $i$ 左边第一个不与 $i$ 重叠的出现 $j$ ，也就是说 $j$ 是最大的使 $pos_i > pos_j + |t| - 1$ 成立的数，我们不需要考虑 $j$ 与 $i$ 之间的位置转移，因为 $j$ 到 $i$ 之间的操作会使 $i$ 位置的出现被部分消除。然后我们再找到最左边与 $j$ 重叠的出现 $k$ ，也就是说 $k$ 是最小是使 $pos_j \ge pos_k + |t| - 1$ 成立的数。 $k$ 左边的出现就不能考虑了因为 $j$ 出现就无法被消除，所以我们考虑从 $k$ 到 $j$ 位置的转移，最终的答案就是所有满足 $last \le pos_i + |t| - 1$ 且 $f_i$ 为最小值的 $i$ 的 $g_i$ 的和，其中 $last$ 为最后一个出现的位置，具体实现详见代码：

#include <bits/stdc++.h>
using namespace std;
 
template <int MOD>
struct ModInt {
    int val;
    ModInt(long long v = 0) : val(v % MOD) { if (val < 0) val += MOD; };
    ModInt operator+() const { return ModInt(val); }
    ModInt operator-() const { return ModInt(MOD - val); }
    ModInt inv() const {
        auto a = val, m = MOD, u = 0, v = 1;
        while (a != 0) { auto t = m / a; m -= t * a; swap(a, m); u -= t * v; swap(u, v); }
        assert(m == 1);
        return u;
    }
    ModInt pow(long long n) const {
        auto x = ModInt(1);
        auto b = *this;
        while (n > 0) {
            if (n & 1) x *= b;
            n >>= 1;
            b *= b;
        }
        return x;
    }
    friend ModInt operator+ (ModInt lhs, const ModInt& rhs) { return lhs += rhs; }
    friend ModInt operator- (ModInt lhs, const ModInt& rhs) { return lhs -= rhs; }
    friend ModInt operator* (ModInt lhs, const ModInt& rhs) { return lhs *= rhs; }
    friend ModInt operator/ (ModInt lhs, const ModInt& rhs) { return lhs /= rhs; }
    ModInt& operator+=(const ModInt& x) { if ((val += x.val) >= MOD) val -= MOD; return *this; }
    ModInt& operator-=(const ModInt& x) { if ((val -= x.val) < 0) val += MOD; return *this; }
    ModInt& operator*=(const ModInt& x) { val = int64_t(val) * x.val % MOD; return *this; }
    ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }
    bool operator==(const ModInt& b) const { return val == b.val; }
    bool operator!=(const ModInt& b) const { return val != b.val; }
    friend std::istream& operator>>(std::istream& is, ModInt& x) noexcept { return is >> x.val; }
    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }
};
using mint = ModInt<1'000'000'007>;
 
void test_case() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
 
    vector<int> pos;
    for (int i = 0; i + m <= n; i++) {
        if (s.substr(i, m) == t) {
            pos.push_back(i);
        }
    }
    if (pos.empty()) {
        cout << "0 1\n";
        return;
    }
 
    int sz = pos.size();
    vector<int> f(sz, n);
    vector<mint> g(sz);
    for (int i = 0; i < sz; i++) {
        int j = i - 1;
        while (j >= 0 && pos[i] <= pos[j] + m - 1) {
            j--;
        }
        if (j == -1) {
            f[i] = 1;
            g[i] = 1;
        } else {
            for (int k = j; k >= 0 && pos[j] <= pos[k] + m - 1; k--) {
                if (f[k] + 1 < f[i]) {
                    f[i] = f[k] + 1;
                    g[i] = g[k];
                } else if (f[k] + 1 == f[i]) {
                    g[i] += g[k];
                }
            }
        }
    }
    mint ans = 0;
    int mn = f.back();
    for (int i = sz - 1; i >= 0 && pos.back() <= pos[i] + m - 1; i--) {
        if (f[i] < mn) {
            mn = f[i];
            ans = g[i];
        } else if (f[i] == mn) {
            ans += g[i];
        }
    }
    cout << mn << ' ' << ans << '\n';
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        test_case();
    }
}