Editorial for Dư âm cuối thu

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Đọc từng gợi ý khi cần. Gợi ý sâu hơn và lời giải nằm bên trong các khối.

Gợi ý 1

Hãy cố định một độ dài L. Ta cần kiểm tra xem có hai vị trí bắt đầu khác nhau tạo ra cùng một xâu con độ dài L hay không.

Gợi ý 2

Dùng hash tiền tố để lấy hash của mỗi đoạn trong O(1). Duyệt các vị trí bắt đầu, tính cặp hash và lưu các cặp đã gặp trong một tập hợp.

Gợi ý 3

Nếu có xâu con lặp độ dài L, thì với mọi độ dài nhỏ hơn, các tiền tố ở cùng hai vị trí bắt đầu cũng lặp. Tính khả thi có tính đơn điệu, nên ta có thể tìm kiếm nhị phân độ dài.

Lời giải đầy đủ

Cách làm

Với một độ dài len, duyệt mọi xâu con liên tiếp có độ dài len. Hash kép cho mỗi xâu con được lấy từ hai mảng hash tiền tố. Nếu cặp hash đã có trong tập hợp, ta tìm thấy hai lần xuất hiện ở hai vị trí bắt đầu khác nhau.

Hai lần xuất hiện được phép chồng lấp. Ta không cần kiểm tra hai đoạn có rời nhau hay không.

Dùng tìm kiếm nhị phân để tìm độ dài lớn nhất còn khả thi.

Độ phức tạp

Mỗi lần kiểm tra duyệt O(N) đoạn, với thao tác thêm/tìm trong unordered_set có thời gian trung bình O(1). Tổng thời gian trung bình là O(N log N), bộ nhớ O(N).

Mã nguồn C++17
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD1 = 1'000'000'007;
const ll MOD2 = 1'000'000'009;
const ll BASE = 101;

int n;
string s;
vector<ll> h1, h2, p1, p2;

pair<ll, ll> getHash(int left, int len) {
    ll x = (h1[left + len] - h1[left] * p1[len] % MOD1 + MOD1) % MOD1;
    ll y = (h2[left + len] - h2[left] * p2[len] % MOD2 + MOD2) % MOD2;
    return {x, y};
}

bool check(int len) {
    unordered_set<ll> seen;
    seen.reserve(n - len + 1);

    for (int left = 0; left + len <= n; ++left) {
        auto [x, y] = getHash(left, len);
        ll key = x * MOD2 + y; // y < MOD2, so each hash pair has a unique key.
        if (seen.count(key)) return true;
        seen.insert(key);
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s;
    n = static_cast<int>(s.size());

    h1.assign(n + 1, 0);
    h2.assign(n + 1, 0);
    p1.assign(n + 1, 1);
    p2.assign(n + 1, 1);

    for (int i = 0; i < n; ++i) {
        int value = s[i] - 'a' + 1;
        h1[i + 1] = (h1[i] * BASE + value) % MOD1;
        h2[i + 1] = (h2[i] * BASE + value) % MOD2;
        p1[i + 1] = p1[i] * BASE % MOD1;
        p2[i + 1] = p2[i] * BASE % MOD2;
    }

    int low = 1, high = n, answer = 0;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (check(mid)) {
            answer = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    cout << answer << '\n';
    return 0;
}

Loading...