题解：CF2225F String Cutting

Tomwsc · 2026-04-28 13:29:03 · 题解

螳臂题目啊啊啊。

考虑枚举一下每一个位置作为答案起点时的情况，贪心的考虑，肯定越长越好，而这个长度是可以 O(1) 算出来的。具体地说，让答案的前面和后面的串都尽可能的短就行了。同时，考虑实时记录一个答案，然后每次找到一个新串就比较一下字典序。

此时 SA、SAM 都可以随便做了。当然，可以使用二分+哈希找 LCP，然后比较字典序，但是 CF 老传统必卡的好吧。时间复杂度单老哥。

::::success[Code]

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using i128 = __int128;

using PII = pair<int, int>;
using PLL = pair<ll, ll>;

#define fi first
#define se second

constexpr ll inf = (1ll << 62);
constexpr int N = 1e6 + 10, mod1 = 1e9 + 9, mod2 = 1e9 + 7, base = 262;

template <typename T> void chkmax(T& a, T b) { a = max(a, b); }
template <typename T> void chkmin(T& a, T b) { a = min(a, b); }

vector<ll> poww1(N), poww2(N);

void solve() {
    int n, l, k;
    string s;
    cin >> n >> l >> k >> s;
    if (n / l < k) {
        cout << "NO\n";
        return;
    }
    vector<ll> h1(n), h2(n);
    for (int i = 0; i < n; i++) {
        h1[i] = ((!i ? 0 : h1[i - 1] * base % mod1) + s[i] - 'a') % mod1;
        h2[i] = ((!i ? 0 : h2[i - 1] * base % mod2) + s[i] - 'a') % mod2;
    }

    auto get = [&](int l, int r) -> PLL {
        ll a = (h1[r] + mod1 - (!l ? 0 : h1[l - 1] * poww1[r - l + 1] % mod1)) % mod1;
        ll b = (h2[r] + mod2 - (!l ? 0 : h2[l - 1] * poww2[r - l + 1] % mod2)) % mod2;
        return {a, b};
    };

    int L = 0, R = n - (k - 1) * l - 1;
    for (int i = l; i <= n - l; i++) {
        int cur = min(k - 1, i / l), b = n - (k - cur - 1) * l - 1;
        if (b - i + 1 < l || !cur) {
            continue;
        }
        if (L == -1) {
            L = i;
            R = b;
        } else {
            int lb = 0, rb = min(R - L + 1, b - i + 1);
            while (lb < rb) {
                int mid = lb + rb + 1 >> 1;
                if (get(L, L + mid - 1) == get(i, i + mid - 1)) lb = mid;
                else rb = mid - 1;
            }
            if (lb == min(R - L + 1, b - i + 1)) {
                if (R - L + 1 < b - i + 1) {
                    L = i, R = b;
                }
            } else {
                if (s[L + lb] < s[i + lb]) {
                    L = i, R = b;
                }
            }
        }
    }
    cout << "YES\n";
    for (int i = L; i <= R; i++) {
        cout << s[i];
    }
    cout << "\n";
}

int main() {
    poww1[0] = 1;
    poww2[0] = 1;
    for (int i = 1; i < N; i++) {
        poww1[i] = poww1[i - 1] * base % mod1;
        poww2[i] = poww2[i - 1] * base % mod2;
    }
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

::::