Hiểu bài toán

Bài toán yêu cầu tìm số lượng ký tự cần xóa từ xâu P (xâu đã gõ) để thu được xâu I (xâu mong muốn). Điều kiện tiên quyết là P phải chứa I như một xâu con (subsequence) theo đúng thứ tự. Nếu P không chứa I, kết quả là 'IMPOSSIBLE'. Nếu có, số ký tự cần xóa bằng |P| - |I|.

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

Cách Two Pointers (Con trỏ kép)

#include <iostream>
#include <string>
using namespace std;

int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t) {
        string I, P;
        cin >> I >> P;
        int n = I.length();
        int m = P.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (I[i] == P[j]) {
                i++;
            }
            j++;
        }
        cout << "Case #" << t << ": ";
        if (i == n) {
            cout << (m - n) << endl;
        } else {
            cout << "IMPOSSIBLE" << endl;
        }
    }
    return 0;
}

• Time Complexity: O(|P| + |I|)
• Space Complexity: O(1)

Sử dụng hai chỉ số (index), một cho xâu I (i) và một cho xâu P (j). Duyệt qua từng ký tự của P. Nếu ký tự hiện tại của P khớp với ký tự hiện tại của I, ta tiến lên ký tự tiếp theo của I. Cuối cùng, nếu i đã duyệt hết I (i == n), nghĩa là I là xâu con của P. Số ký tự cần xóa là |P| - |I|. Cách này rất hiệu quả và chỉ cần duyệt qua P một lần.

Cách Duyệt tuần tự với biến đếm

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

int main() {
    int n;
    cin >> n;
    cin.ignore();
    for (int i = 0; i < n; i++) {
        string a, b;
        cin >> a >> b;
        int x = a.size();
        int y = b.size();
        int k = 0, j = 0;
        while (k < x && j < y) {
            if (a[k] == b[j]) {
                k++;
            }
            j++;
        }
        cout << "Case " << "#" << i + 1 << ": ";
        if (k == x) {
            cout << y - x << endl;
        } else {
            cout << "IMPOSSIBLE" << endl;
        }
    }
    return 0;
}

• Time Complexity: O(|P| + |I|)
• Space Complexity: O(1)

Đây là biến thể của phương pháp Two Pointers. Logic cơ bản giống hệt: duyệt qua P (biến j) và so khớp với I (biến k). Nếu khớp thì tăng k. Kiểm tra điều kiện vòng lặp để đảm bảo không truy cập ngoài biên. Cuối cùng so sánh k với độ dài của I để xác định có tìm thấy đủ hay không.

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

Bài học kinh nghiệm

• Vấn đề có thể được suy nghĩ đơn giản là kiểm tra xem xâu I có phải là xâu con (subsequence) của xâu P hay không.
• Nếu I là xâu con của P, số ký tự thừa cần xóa chính là hiệu số độ dài của hai xâu (|P| - |I|).
• Sử dụng kỹ thuật Two Pointers là cách tiếp cận tối ưu nhất với độ phức tạp thời gian tuyến tính O(N).

Lỗi thường gặp

• Lầm tưởng rằng chỉ cần kiểm tra xem I có nằm trong P (vị trí bất kỳ) hay không (sử dụng hàm find), nhưng vấn đề yêu cầu I phải xuất hiện theo đúng thứ tự tự nhiên trong P.
• Xử lý sai trường hợp P ngắn hơn I: theo đề bài, nếu P ngắn hơn thì chắc chắn không thể tạo ra I (do chỉ được xóa ký tự, không được thêm). Tuy nhiên, thuật toán Two Pointers chuẩn vẫn xử lý đúng vì vòng lặp sẽ kết thúc trước khi duyệt hết I.
• Bỏ qua việc kiểm tra độ dài P và I trước khi xử lý có thể gây ra kết quả sai logic (ví dụ in ra số âm nếu P ngắn hơn I trong cách tiếp cận không kiểm tra kỹ).