In tất cả cách biến đổi chuỗi này thành chuỗi kia trong C++

Giới thiệu

Cho 2 xâu str1, str2. Tìm các phép biến đổi (Insert, Delete, Replace) để chuyển str1 thành str2. Đây là bài toán Edit Distance mở rộng: in ra các thao tác cụ thể.

Thuật toán: Dynamic Programming + Traceback

1. Xây bảng DP[i][j] = edit distance từ str1[0..i-1] đến str2[0..j-1]
2. Traceback từ DP[n][m] về DP[0][0] để tìm các thao tác

Công thức DP

DP[i][j] = min(
    DP[i-1][j-1] + (str1[i-1] != str2[j-1]),  // Replace/Match
    DP[i-1][j] + 1,                            // Delete
    DP[i][j-1] + 1                             // Insert
)

Mã nguồn hoàn chỉnh

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

const int MAX = 100;
int dp[MAX][MAX];

void findEditOperations(string str1, string str2) {
    int n = str1.length(), m = str2.length();
    
    // Khởi tạo
    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;
    
    // Điền bảng DP
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]});
            }
        }
    }
    
    // Traceback để tìm các thao tác
    int i = n, j = m;
    vector operations;
    
    while (i > 0 || j > 0) {
        if (i > 0 && j > 0 && str1[i-1] == str2[j-1]) {
            i--; j--; // Match, không có thao tác
        } else if (i > 0 && j > 0 && dp[i][j] == dp[i-1][j-1] + 1) {
            operations.push_back("Replace '" + string(1, str1[i-1]) + 
                               "' with '" + string(1, str2[j-1]) + "'");
            i--; j--;
        } else if (i > 0 && dp[i][j] == dp[i-1][j] + 1) {
            operations.push_back("Delete '" + string(1, str1[i-1]) + "'");
            i--;
        } else if (j > 0 && dp[i][j] == dp[i][j-1] + 1) {
            operations.push_back("Insert '" + string(1, str2[j-1]) + "'");
            j--;
        }
    }
    
    // In ngược lại (từ đầu đến cuối)
    reverse(operations.begin(), operations.end());
    for (int k = 0; k < operations.size(); k++) {
        cout << "Step " << (k+1) << ": " << operations[k] << endl;
    }
    cout << "Min operations: " << operations.size() << endl;
}

int main() {
    string str1 = "kfeodge";
    string str2 = "kfcadqpe";
    
    cout << "Chuyen '" << str1 << "' -> '" << str2 << "':" << endl;
    findEditOperations(str1, str2);
    
    return 0;
}

Kết quả chạy chương trình

Chuyen 'kfeodge' -> 'kfcadqpe':
Step 1: Replace 'e' with 'c'
Step 2: Replace 'o' with 'a'
Step 3: Delete 'd'
Step 4: Delete 'g'
Step 5: Insert 'q'
Step 6: Insert 'p'
Step 7: Insert 'e'
Min operations: 7

Lưu ý: In TẤT CẢ cách biến đổi

Code trên in một cách tối ưu. Để in tất cả cách (có số lượng mũ), cần backtracking đệ quy với vector lưu đường đi, rất phức tạp hơn.

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

• DP table: O(n×m) thời gian, O(n×m) không gian
• Traceback: O(n+m)

Ứng dụng

• Spell checker, autocorrect
• DNA sequence alignment (bioinformatics)
• Diff tools (git diff, so sánh file)
• Natural Language Processing

Kết luận

Edit Distance với traceback là bài toán DP kinh điển. In một cách tối ưu dễ dàng, in tất cả cách cần backtracking phức tạp hơn nhiều.