Hướng dẫn cho LQDOJ CUP 2022 - Round 2 - MINSTR

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: nhphucqt

Subtask 1 (\(20\%\) số điểm): \(N \le 10 ^ 2\), \(T \le 10 ^ 2\).

Tutorial

Với mỗi xâu \(B_i\) \((1 \leq i \leq N)\), duyệt từng xâu con của \(B_i\) và với mỗi xâu trong \(M\) xâu cho trước, sử dụng quy hoạch động để tìm ra xâu con chung dài nhất của hai xâu. Độ dài nhỏ nhất trong các xâu con chung dài nhất khi xét từng xâu \(B_i\) là kết quả của bài toán.
Độ phức tạp: \(\mathcal{O}(N^3)\).

Solution
C++
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int MAX_M = 10005;

int n, m;
string str;
string arr[MAX_N];

int lcs(string a, string b) {
    int lengthA = a.length();
    int lengthB = b.length();
    a = " " + a;
    b = " " + b;

    int result = 0;
    vector<vector<int>> dp = vector<vector<int>>(a.size(), vector<int>(b.size(), 0));
    for (int i = 1; i <= lengthA; i++) {
        for (int j = 1; j <= lengthB; j++) {
            dp[i][j] = (a[i] == b[j] ? dp[i - 1][j - 1] + 1 : 0);
            result = max(result, dp[i][j]);
        }
    }

    return result;
}

int solve() {
    int result = 0;
    for (int i = 1; i <= m; i++) {
        result = max(result, lcs(str, arr[i]));
    }
    return result;
}

void nextStr() {
    reverse(str.begin(), str.end());
    char ch = str.back();
    str.pop_back();
    reverse(str.begin(), str.end());
    str.push_back(ch);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("MINSTR.inp", "r", stdin);
    freopen("MINSTR.out", "w", stdout);

    cin >> n >> m;
    cin >> str;
    for (int i = 1; i <= m; i++) {
        cin >> arr[i];
    }

    int answer = n;
    for (int i = 1; i <= n; i++) {
        answer = min(answer, solve());
        nextStr();
    }

    cout << answer;

    return 0;
}

Subtask \(2\) (\(20\%\) số điểm): \(N \le 10 ^ 3\), \(T \le 10 ^ 3\).

Tutorial

Đầu tiên, lưu các giá trị hash của từng xâu con của \(M\) xâu (lưu dưới dạng cặp [<giá trị hash>, <độ dài xâu con>] để tăng độ chính xác) vào một cấu trúc dữ liệu như map hoặc set hoặc lưu vào mảng rồi sắp xếp lại (tìm trong \(O(\log N)\)).
Chặt nhị phân kết quả \(x\), nếu tất cả các xâu \(B_i\) \((1 \leq i \leq N)\) đều có ít nhất một xâu con độ dài \(x\) là xâu con của ít nhất một trong \(M\) xâu đã cho (kiểm tra bằng hash) thì độ xấu của \(B_i \geq x\), vậy nên kết quả cần tìm \(\geq x\). Ngược lại thì kết quả cần tìm \(< x\).
Độ phức tạp: \(\mathcal{O}\left(T^2 \cdot \log T^2 + N^2 \cdot \log N \cdot \log T^2\right)\).

Solution
C++
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int MAX_M = 10005;
const long long BASE = 37;
const long long MOD1 = 1000000007;
long long powerBase1[MAX_N];

struct Hash {
    int len;
    vector<long long> val1, val2;
    void init(string s) {
        len = s.length();
        s = '0' + s;
        val1.assign(len + 1, 0);
        val2.assign(len + 1, 0);
        for (int i = 1; i <= len; i++) {
            val1[i] = (val1[i - 1] * BASE + (s[i] - 'a')) % MOD1;
        }
    }
    int get(int left, int right) {
        return (val1[right] - val1[left - 1] * powerBase1[right - left + 1] + MOD1 * MOD1) % MOD1;
    }
};

void prepare_hash() {
    powerBase1[0] = 1;
    for (int i = 1; i < MAX_N; i++) {
        powerBase1[i] = powerBase1[i - 1] * BASE % MOD1;
    }
}

int n, m;
string str;
string b[MAX_N];
string arr[MAX_M];
Hash hashCode[MAX_N];
set<int> hashCodeArr[MAX_N];

void nextStr() {
    reverse(str.begin(), str.end());
    char ch = str.back();
    str.pop_back();
    reverse(str.begin(), str.end());
    str.push_back(ch);
}

void addHashCodeArr(string str) {
    int lengthStr = str.size();
    Hash hash;
    hash.init(str);
    for (int i = 1; i <= lengthStr; i++) {
        for (int j = i; j <= lengthStr; j++) {
            hashCodeArr[j - i + 1].insert(hash.get(i, j));
        }
    }
}

void initialize() {
    for (int i = 1; i <= n; i++) {
        b[i] = str;
        hashCode[i].init(b[i]);
        nextStr();
    }

    for (int id = 1; id <= m; id++) {
        addHashCodeArr(arr[id]);
    }
}

bool check(int length) {
    for (int id = 1; id <= n; id++) {
        bool hasSubstring = false;
        for (int i = 1; i <= n - length + 1; i++) {
            if (hashCodeArr[length].count(
                    hashCode[id].get(i, i + length - 1))) {
                hasSubstring = true;
                break;
            }
        }
        if (!hasSubstring) {
            return true;
        }
    }
    return false;
}

int binarySearch(int left, int right) {
    while (left <= right) {
        int mid = (left + right) / 2;
        check(mid) ? right = mid - 1 : left = mid + 1;
    }
    return right;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("MINSTR.inp", "r", stdin);
    freopen("MINSTR.out", "w", stdout);

    prepare_hash();

    cin >> n >> m;
    cin >> str;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    initialize();

    int answer = binarySearch(1, n);
    cout << answer;

    return 0;
}

Subtask \(3\) (\(20\%\) số điểm): \(T \le 10 ^ 3\).

Tutorial

Chặt nhị phân kết quả \(x\), để kiểm tra liệu tất cả xâu \(B_i\) có độ xấu \(\geq x\) hay không thì ta làm như sau:

  • Gấp đôi xâu \(A\), xét một đoạn độ dài \(x\) là \([i, i + x - 1]\), ta sẽ biết đoạn này có là xâu con của ít nhất một xâu trong \(M\) cho trước hay không (kiểm tra bằng giá trị hash).
  • Nhận thấy đoạn xâu \([i, i + x - 1]\) là xâu con của các xâu \(B_k\) với \(k\) thuộc \([\max(1, i + x - N), \min(N, i)]\), vậy nên nếu đoạn xâu \([i, i + x - 1]\) là xâu con của một trong \(M\) xâu đã cho thì các xâu \(B_k\) với \(k\) thuộc đoạn giá trị trên sẽ có độ xấu \(\geq x\).
  • Sử dụng kĩ thuật mảng cộng dồn, ta tăng đoạn \([\max(1, i + x - N), \min(N, i)]\) lên \(1\).
  • Sau khi duyệt xong hết tất cả các đoạn \([i, i + x - 1]\), nếu tồn tại một vị trí \(j\) mà ở đó tổng cộng dồn bằng \(0\) thì suy ra \(B_j\) không có xâu con độ dài \(x\) nào là xâu con của ít nhất một xâu trong \(M\) xâu cho trước, tức là kết quả cần tìm \(\geq x\). Ngược lại thì kết quả cần tìm \(< x\).

Độ phức tạp: \(\mathcal{O}\left(T^2 \cdot \log T^2 + N \cdot \log N \cdot \log T^2\right)\).

Solution
C++
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int MAX_M = 10005;

const long long BASE = 37;
const long long MOD1 = 1000000007;
const long long MOD2 = 1000000009;

long long powerBase1[MAX_N], powerBase2[MAX_N];

struct Hash {
    int len;
    vector<long long> val1, val2;
    void init(string s) {
        len = s.length();
        s = '0' + s;
        val1.assign(len + 1, 0);
        val2.assign(len + 1, 0);
        for (int i = 1; i <= len; i++) {
            val1[i] = (val1[i - 1] * BASE + (s[i] - 'a')) % MOD1;
            val2[i] = (val2[i - 1] * BASE + (s[i] - 'a')) % MOD2;
        }
    }
    pair<int, int> get(int left, int right) {
        return make_pair(int((val1[right] - val1[left - 1] * powerBase1[right - left + 1] + MOD1 * MOD1) % MOD1),
                        int((val2[right] - val2[left - 1] * powerBase2[right - left + 1] + MOD2 * MOD2) % MOD2));
    }
};

void prepare_hash() {
    powerBase1[0] = 1;
    powerBase2[0] = 1;
    for (int i = 1; i < MAX_N; i++) {
        powerBase1[i] = powerBase1[i - 1] * BASE % MOD1;
        powerBase2[i] = powerBase2[i - 1] * BASE % MOD2;
    }
}

int n, m;
string str;
string arr[MAX_M];
Hash hashCode;
set<pair<int, int>> hashCodeArr[MAX_N];
void addHashCodeArr(string str) {
    int lengthStr = str.size();
    Hash hash;
    hash.init(str);
    for (int i = 1; i <= lengthStr; i++) {
        for (int j = i; j <= lengthStr; j++) {
            hashCodeArr[j - i + 1].insert(hash.get(i, j));
        }
    }
}

void initialize() {
    str = str + str;
    hashCode.init(str);

    for (int id = 1; id <= m; id++) {
        addHashCodeArr(arr[id]);
    }
}

bool check(int length) {
    int last = 0;
    for (int i = 1; i <= n * 2 - length + 1; i++) {
        if (hashCodeArr[length].count(hashCode.get(i, i + length - 1))) {
            last = i;
        } else if (i - last >= n - length + 1) {
            return true;
        }
    }
    return false;
}

int binarySearch(int left, int right) {
    while (left <= right) {
        int mid = (left + right) / 2;
        check(mid) ? right = mid - 1 : left = mid + 1;
    }
    return right;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("MINSTR.inp", "r", stdin);
    freopen("MINSTR.out", "w", stdout);

    prepare_hash();

    cin >> n >> m;
    cin >> str;
    for (int i = 1; i <= m; i++) {
        cin >> arr[i];
    }

    initialize();

    int answer = binarySearch(1, n);
    cout << answer;

    return 0;
}

Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Tutorial

Thuật toán tương tự subtask 3 nhưng thay vì lưu trước hết \(T^2\) xâu con của \(M\) xâu cho trước thì với mỗi lần chặt nhị phân kết quả \(x\), ta chỉ lưu các xâu con độ dài \(x\).
Độ phức tạp: \(\mathcal{O}\left(T \cdot \log T \cdot \log N + N \cdot \log T \cdot \log N\right)\).

Solution
C++
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int MAX_M = 10005;

const long long BASE = 37;
const long long MOD1 = 1000000007;
const long long MOD2 = 1000000009;

long long powerBase1[MAX_N], powerBase2[MAX_N];

struct Hash {
    int len;
    vector<long long> val1, val2;
    void init(string s) {
        len = s.length();
        s = '0' + s;
        val1.assign(len + 1, 0);
        val2.assign(len + 1, 0);
        for (int i = 1; i <= len; i++) {
            val1[i] = (val1[i - 1] * BASE + (s[i] - 'a')) % MOD1;
            val2[i] = (val2[i - 1] * BASE + (s[i] - 'a')) % MOD2;
        }
    }
    pair<int, int> get(int left, int right) {
        return make_pair(int((val1[right] - val1[left - 1] * powerBase1[right - left + 1] + MOD1 * MOD1) % MOD1),
                        int((val2[right] - val2[left - 1] * powerBase2[right - left + 1] + MOD2 * MOD2) % MOD2));
    }
};

void prepare_hash() {
    powerBase1[0] = 1;
    powerBase2[0] = 1;
    for (int i = 1; i < MAX_N; i++) {
        powerBase1[i] = powerBase1[i - 1] * BASE % MOD1;
        powerBase2[i] = powerBase2[i - 1] * BASE % MOD2;
    }
}

int n, m;
string str;
string arr[MAX_M];
Hash hashCode;
Hash hashCodeArr[MAX_N];

void initialize() {
    str = str + str;
    hashCode.init(str);

    for (int id = 1; id <= m; id++) {
        hashCodeArr[id].init(arr[id]);
    }
}

bool check(int length) {
    set<pair<int, int>> hashCodeOfLength;
    for (int id = 1; id <= m; id++) {
        for (int i = 1; i <= hashCodeArr[id].len - length + 1; i++) {
            hashCodeOfLength.insert(hashCodeArr[id].get(i, i + length - 1));
        }
    }

    int last = 0;
    for (int i = 1; i <= n * 2 - length + 1; i++) {
        if (hashCodeOfLength.count(hashCode.get(i, i + length - 1))) {
            last = i;
        } else if (i - last >= n - length + 1) {
            return true;
        }
    }
    return false;
}

int binarySearch(int left, int right) {
    while (left <= right) {
        int mid = (left + right) / 2;
        check(mid) ? right = mid - 1 : left = mid + 1;
    }
    return right;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("MINSTR.inp", "r", stdin);
    freopen("MINSTR.out", "w", stdout);

    prepare_hash();

    cin >> n >> m;
    cin >> str;
    for (int i = 1; i <= m; i++) {
        cin >> arr[i];
    }

    initialize();

    int answer = binarySearch(1, n);
    cout << answer;

    return 0;
}

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.