Thuật Toán Cửa Sổ Trượt

1. Khái niệm

Cửa sổ trượt là một kỹ thuật dựa trên nguyên tắc con trỏ kép, trong đó hai con trỏ xác định một khoảng các phần tử tạo thành một "cửa sổ" trên cấu trúc dữ liệu.

2. Phân loại

Cửa sổ trượt có hai loại chính: cửa sổ có kích thước cố định và cửa sổ có kích thước thay đổi linh hoạt.

3. Ứng dụng thực tế

Kỹ thuật cửa sổ trượt thường được sử dụng để xử lý dữ liệu có tính liên tục, như tính trung bình động của các giá trị theo thời gian, giúp kết quả ổn định hơn (ví dụ: giám sát nhiệt độ).

Các bài toán nào có thể giải quyết bằng kỹ thuật cửa sổ trượt?

• Dữ liệu đầu thường là mảng hoặc chuỗi ký tự
• Tìm kiếm chuỗi con hoặc dãy con có độ dài lớn nhất/nhỏ nhất hoặc đạt giá trị mục tiêu
• Bài toán có thể giải quyết bằng phương pháp brute force nhưng cần tối ưu hóa

4. Nguyên tắc hoạt động

1. Sử dụng kỹ thuật con trỏ trái và phải trên chuỗi, khởi tạo left = right = 0. Khoảng đóng [left, right] được gọi là cửa sổ.
2. Tăng liên tục right để mở rộng cửa sổ [left, right] cho đến khi các phần tử trong cửa sổ thỏa mãn yêu cầu.
Khi đã tìm được cửa sổ thỏa mãn, ngừng tăng right và bắt đầu tăng left để thu hẹp cửa sổ [left, right] cho đến khi cửa sổ không còn thỏa mãn. Trước mỗi lần tăng left, cập nhật kết quả.
3. Lặp lại bước 2 và 3 cho đến khi right đạt đến cuối chuỗi.

Ý tưởng cơ bản: bước 2 tìm kiếm một lời giải khả thi, bước 3 tối ưu hóa lời giải này để tìm ra lời giải tối ưu.

5. Mẫu thuật toán

(1) Mẫu đơn vòng lặp - Phù hợp với cửa sổ cố định

def slidingWindowFixed():
    # Khởi tạo hai đầu cửa sổ
    left = right = 0
    
    # Dữ liệu và độ dài
    data, data_len = [], 0
    
    # Cửa sổ trượt
    window = []
    
    # Kết quả
    result = 0
    
    while right < data_len:
        window.append(data[right])
        # Nếu chưa tìm được lời giải khả thi
        if not is_valid(window):
            # Mở rộng cửa sổ
            right += 1
        else:
            # Tìm thấy lời giải, cập nhật kết quả
            result = update_result(result, window)
            # Thu hẹp cửa sổ
            left += 1

(2) Mẫu kép vòng lặp - Phù hợp với cửa sổ động

def slidingWindowDynamic():
    # Khởi tạo hai đầu cửa sổ
    left = right = 0
    
    # Dữ liệu và độ dài
    data, data_len = [], 0
    
    # Cửa sổ trượt
    window = []
    
    # Kết quả
    result = 0
    
    while right < data_len:
        window.append(data[right])
        # Nếu chưa tìm được lời giải khả thi
        if not is_valid(window):
            # Mở rộng cửa sổ
            right += 1
            continue
        
        # Cập nhật và tối ưu lời giải khả thi
        while is_valid(window):
            # Tìm thấy lời giải, cập nhật kết quả
            result = update_result(result, window)
            # Thu hẹp cửa sổ
            left += 1

6. Ví dụ thực hành

(1) Cửa sổ cố định - Tìm tất cả vị trí của các từ vịn

vector<int> timViTriTuAn(string chuoi, string mau)
{
    vector<int> demMau(26, 0);
    vector<int> demCuaSo(26, 0);
    vector<int> ketQua;
    
    // Đếm tần suất ký tự từ mẫu
    for (char c : mau) {
        demMau[c - 'a']++;
    }
    
    // Duyệt chuỗi chính
    for (int i = 0; i < chuoi.length(); i++) {
        demCuaSo[chuoi[i] - 'a']++;
        
        // Giữ kích thước cửa sổ bằng độ dài mẫu
        if (i >= mau.length()) {
            demCuaSo[chuoi[i - mau.length()] - 'a']--;
        }
        
        // So sánh tần suất
        if (demMau == demCuaSo) {
            ketQua.push_back(i - mau.length() + 1);
        }
    }
    
    return ketQua;
}

(2) Cửa sổ động - Tìm chuỗi con nhỏ nhất chứa tất cả ký tự

string chuoiConNhoNhat(string s, string t)
{
    string ketQua;
    if (s.empty() || t.empty()) return ketQua;
    
    unordered_map yeuCau;
    unordered_map cuaSo;
    
    // Đếm tần suất ký tự cần tìm
    for (char c : t) {
        yeuCau[c]++;
    }
    
    int minDoDai = INT_MAX;
    int demKyTu = 0;
    
    for (int trai = 0, phai = 0; phai < s.length(); phai++) {
        char hienTai = s[phai];
        
        // Nếu ký tự hiện tại là ký tự cần tìm
        if (yeuCau.find(hienTai) != yeuCau.end()) {
            cuaSo[hienTai]++;
            
            // Đếm nếu tần suất không vượt quá yêu cầu
            if (cuaSo[hienTai] <= yeuCau[hienTai]) {
                demKyTu++;
            }
        }
        
        // Nếu đã có đủ các ký tự cần thiết
        if (demKyTu >= t.length()) {
            // Thu hẹp cửa sổ từ phía trái
            while (yeuCau.find(s[trai]) == yeuCau.end() || 
                   cuaSo[s[trai]] > yeuCau[s[trai]]) {
                cuaSo[s[trai]]--;
                trai++;
            }
            
            // Cập nhật kết quả nếu tìm thấy chuỗi nhỏ hơn
            if ((phai - trai + 1) < minDoDai) {
                minDoDai = phai - trai + 1;
                ketQua = s.substr(trai, minDoDai);
            }
        }
    }
    
    return ketQua;
}