Hướng dẫn giải của TÁCH XÂU

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, Yamiza_Zinno, nttxn24, tranhaiancpp

Hiểu bài toán

Cho hai xâu ký tự S độ dài N và T độ dài M. Tìm cách chọn đúng K đoạn con liên tiếp (không rỗng) trên S và K đoạn con tương ứng trên T sao cho các đoạn này tương ứng với nhau (tức là xâu con trong S lấy ra phải trùng khớp hoàn toàn với xâu con trong T lấy ra). Tổng độ dài của tất cả các đoạn được chọn phải là lớn nhất có thể. Nếu không có cách chọn thỏa mãn, in ra -1.

Giải thích chi tiết:

  • 'Tương ứng' ở đây có nghĩa là các đoạn được chọn trên S và T phải tạo ra các cặp xâu con bằng nhau.
  • Ví dụ: S = 'abc', T = 'axc', K = 1. Ta có thể chọn đoạn 'a' ở cả hai (vị trí 1), hoặc 'c' (vị trí 3). Tổng độ dài max là 1. Nếu K = 2, ta cần chọn 2 cặp, nhưng không thể chọn 2 cặp xâu con bằng nhau (vì chỉ có 'a' và 'c' chung), đáp án là -1.
  • Bài toán yêu cầu tối đa hóa tổng độ dài K đoạn con này.

Các cách tiếp cận

Cách Quy hoạch động cơ bản với Lặp Đo (Loop Segment)
#include <bits/stdc++.h>
using namespace std;

int n, m, k;
string s, t;
int dp[1005][1005][15]; // dp[i][j][p]: độ dài lớn nhất khi xét S[0..i-1], T[0..j-1] với p đoạn

int main() {
    freopen("SPLIT.INP", "r", stdin);
    freopen("SPLIT.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> k;
    cin >> s >> t;

    // Khởi tạo dp bằng -1 (không thể)
    memset(dp, -1, sizeof(dp));

    // Trường hợp 0 đoạn
    for (int i = 0; i <= n; i++) 
        for (int j = 0; j <= m; j++) 
            dp[i][j][0] = 0;

    for (int p = 1; p <= k; p++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 1. Bỏ qua ký tự s[i-1] hoặc t[j-1]
                int res = -1;
                if (dp[i-1][j][p] != -1) res = max(res, dp[i-1][j][p]);
                if (dp[i][j-1][p] != -1) res = max(res, dp[i][j-1][p]);

                // 2. Tạo đoạn mới kết thúc tại (i, j)
                if (s[i-1] == t[j-1]) {
                    // Thử các độ dài đoạn khác nhau
                    for (int len = 1; len <= min(i, j); len++) {
                        if (s[i-len] != t[j-len]) break;
                        if (dp[i-len][j-len][p-1] != -1) {
                            res = max(res, dp[i-len][j-len][p-1] + len);
                        }
                    }
                }
                dp[i][j][p] = res;
            }
        }
    }

    if (dp[n][m][k] <= 0) cout << -1;
    else cout << dp[n][m][k];
    return 0;
}
  • Time Complexity: O(N * M * K * min(N, M)) - Quá chậm cho dữ liệu lớn
  • Space Complexity: O(N * M * K)

Cách tiếp cận này sử dụng quy hoạch động 3 chiều dp[i][j][p]. Trạng thái dp[i][j][p] lưu độ dài lớn nhất của p đoạn con chung trong tiền tố S[0..i-1] và T[0..j-1]. Để tính dp[i][j][p], ta có 2 trường hợp:

  1. Không dùng ký tự s[i-1] hoặc t[j-1]: Lấy giá trị từ dp[i-1][j][p] hoặc dp[i][j-1][p].
  2. Dùng ký tự s[i-1] và t[j-1] để đóng một đoạn con chung: Nếu s[i-1] == t[j-1], ta duyệt ngược lại để tìm độ dài đoạn con chung dài nhất kết thúc tại đây (len). Sau đó cập nhật dp[i][j][p] từ dp[i-len][j-len][p-1] + len. Cách này đúng nhưng chậm vì lặp qua tất cả độ dài đoạn có thể.
Cách Quy hoạch động tối ưu (LCS Suffix)
#include <bits/stdc++.h>
using namespace std;

const int INF = -1e9;

int main() {
    freopen("SPLIT.inp", "r", stdin);
    freopen("SPLIT.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, K;
    cin >> n >> m >> K;
    string s, t;
    cin >> s >> t;
    s = " " + s;
    t = " " + t;

    // lcsuff[i][j]: độ dài đoạn chung dài nhất kết thúc tại s[i], t[j]
    vector<vector<int>> lcsuff(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i] == t[j]) lcsuff[i][j] = lcsuff[i - 1][j - 1] + 1;
        }
    }

    // dp[i][j][c] = tổng độ dài lớn nhất khi xét tiền tố s[1..i], t[1..j], có c đoạn
    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(K + 1, INF)));

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int c = 1; c <= K; c++) {
                // 1. Bỏ qua ký tự s[i] hoặc t[j]
                dp[i][j][c] = max(dp[i - 1][j][c], dp[i][j - 1][c]);

                // 2. Tạo đoạn mới kết thúc tại (i, j)
                // Chỉ cần xét độ dài đoạn = lcsuff[i][j] (vì nếu đoạn dài hơn, nó sẽ được xử lý ở dp[i-1][j-1])
                int len = lcsuff[i][j];
                if (len > 0 && dp[i - len][j - len][c - 1] != INF) {
                    dp[i][j][c] = max(dp[i][j][c], dp[i - len][j - len][c - 1] + len);
                }
            }
        }
    }

    if (dp[n][m][K] < 0) cout << -1;
    else cout << dp[n][m][K];
}
  • Time Complexity: O(N * M * K)
  • Space Complexity: O(N * M * K)

Nâng cấp từ cách 1. Thay vì lặp qua tất cả độ dài đoạn con chung, ta chỉ cần quan tâm đến độ dài đoạn con chung dài nhất kết thúc tại (i, j) - gọi là lcsuff[i][j]. Tại sao chỉ cần xét đoạn dài nhất? Vì nếu ta chọn một đoạn con chung ngắn hơn đoạn dài nhất, ta sẽ bị mất độ dài mà không có lợi ích gì về số lượng đoạn (vì ta vẫn chỉ tạo ra 1 đoạn). Do đó, chỉ cần cân nhắc việc tạo đoạn với độ dài tối đa có thể tại vị trí này. Truy hồi: dp[i][j][c] = max(dp[i-1][j][c], dp[i][j-1][c], dp[i-len][j-len][c-1] + len) với len = lcsuff[i][j].

Cách Quy hoạch động nâng cao (State Machine)
#include <bits/stdc++.h>
using namespace std;

int n, m, k;
string s, t;
// dp[i][j][g][st]: tổng độ dài lớn nhất
// st = 0: đang không ở trong một đoạn chung
// st = 1: đang ở trong một đoạn chung (đã đếm 1 đoạn)
int dp[1005][1005][12][2];

void update(int &a, int b) {
    a = max(a, b);
}

int main() {
    if (fopen("split.inp", "r")) {
        freopen("split.inp", "r", stdin);
        freopen("split.out", "w", stdout);
    }

    cin >> n >> m >> k;
    cin >> s >> t;

    // Khởi tạo -1 (không thể)
    memset(dp, -1, sizeof(dp));

    dp[0][0][0][0] = 0;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int g = 0; g <= k; g++) {
                for (int st = 0; st <= 1; st++) {
                    if (dp[i][j][g][st] == -1) continue;

                    // Nhảy (Bỏ qua ký tự hiện tại)
                    // Nếu đang ở state 0, có thể nhảy thoải mái.
                    // Nếu đang ở state 1, coi như đoạn chung đã kết thúc trước đó.
                    if (i < n) update(dp[i + 1][j][g][0], dp[i][j][g][st]);
                    if (j < m) update(dp[i][j + 1][g][0], dp[i][j][g][st]);

                    // Match (Tạo/Mở rộng đoạn chung)
                    if (i < n && j < m && s[i] == t[j]) {
                        if (st == 0) {
                            // Mở đầu 1 đoạn mới, tăng g lên 1
                            update(dp[i + 1][j + 1][g + 1][1], dp[i][j][g][st] + 1);
                        } else {
                            // Đang ở trong đoạn, tiếp tục (g không tăng)
                            update(dp[i + 1][j + 1][g][1], dp[i][j][g][st] + 1);
                        }
                    }
                }
            }
        }
    }

    int ans = -1;
    // Câu trả lời có thể là state 0 hoặc 1 ở cuối (state 1意味 đoạn chung kết thúc ở cuối xâu)
    ans = max(ans, dp[n][m][k][0]);
    ans = max(ans, dp[n][m][k][1]);

    if (ans < 0) cout << -1;
    else cout << ans;
    return 0;
}
  • Time Complexity: O(N * M * K)
  • Space Complexity: O(N * M * K)

Cách tiếp cận này mô hình hóa bài toán như một automaton (máy trạng thái).

  • State [i][j][g][st]: g là số đoạn đã tạo, st là trạng thái có đang trong đoạn chung hay không.
  • Các bước chuyển:
    1. Nhảy (Skip): Tăng i hoặc j, giữ nguyên g. Nếu đang ở st=1 (trong đoạn), việc nhảy coi như chấm dứt đoạn hiện tại và chuyển sang st=0.
    2. Match (Kết hợp): Nếu s[i] == t[j]:
      • Nếu st=0 (chưa trong đoạn): Tăng g lên 1, chuyển sang st=1, cộng 1 độ dài.
      • Nếu st=1 (đang trong đoạn): Giữ nguyên g, ở lại st=1, cộng 1 độ dài. Cách này xử lý được các trường hợp đoạn chung một cách linh hoạt bằng cách duy trì trạng thái 'đang ở trong đoạn'.

Phân tích độ phức tạp

Cách tiếp cận Time Space Tên
1 O(N * M * K * min(N, M)) - Quá chậm cho dữ liệu lớn O(N * M * K) Quy hoạch động cơ bản với Lặp Đo (Loop Segment)
2 O(N * M * K) O(N * M * K) Quy hoạch động tối ưu (LCS Suffix)
3 O(N * M * K) O(N * M * K) Quy hoạch động nâng cao (State Machine)

Bài học kinh nghiệm

  • Bài toán có thể coi là tìm cách chọn K xâu con chung (Common Substrings) sao cho tổng độ dài lớn nhất.
  • Các đoạn con chung không được phép giao nhau (vì nếu giao nhau, ta có thể gộp chúng lại thành một đoạn dài hơn hoặc chia nhỏ ra để tăng số lượng đoạn).
  • Cần phân biệt giữa 'LCS (Longest Common Subsequence)' (không cần liên tiếp) và 'Common Substrings' (cần liên tiếp). Bài này là biến thể của Common Substrings.

Lỗi thường gặp

  • Đánh đồng bài toán với LCS: Nếu chỉ tìm LCS của K đoạn, ta có thể bị sai vì LCS không yêu cầu các đoạn phải tách biệt hoàn toàn (không giao nhau trong chuỗi S hoặc T).
  • Xử lý số đoạn bằng 0: Đảm bảo dp[][0] = 0.
  • Trường hợp không tìm thấy: Nếu không có K đoạn con chung, cần in ra -1 (đặc biệt quan trọng khi dp trả về 0 hoặc giá trị âm).
  • Lỗi truy cập mảng: Cẩn thận với chỉ số i, j khi chuyển từ 0-based sang 1-based hoặc ngược lại.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.