Trong lập trình, việc xử lý các số nguyên cực lớn vượt quá giới hạn của kiểu dữ liệu long long thường yêu cầu chúng ta phải làm việc trực tiếp trên chuỗi (string). Bài toán "Multiply Strings" yêu cầu thực hiện phép nhân hai chuỗi số nguyên không âm mà không được sử dụng các thư viện hỗ trợ số lớn có sẵn hoặc ép kiểu trực tiếp toàn bộ chuỗi sang số nguyên.

Yêu cầu bài toán

Cho hai chuỗi num1 và num2, hãy trả về tích của chúng dưới dạng một chuỗi. Các ràng buộc chính bao gồm:

• Độ dài của cả hai chuỗi không quá 110 ký tự.
• Chuỗi chỉ chứa các chữ số từ '0' đến '9'.
• Không bắt đầu bằng chữ số 0, ngoại trừ chính số 0.
• Không sử dụng các hàm chuyển đổi chuỗi thành số nguyên có sẵn như stoi.

Giải pháp 1: Mô phỏng phép cộng lặp lại (Naive Approach)

Ý tưởng cơ bản nhất là chia nhỏ phép nhân thành các phép cộng. Chúng ta xây dựng một hàm bổ trợ để cộng hai chuỗi số lớn, sau đó thực hiện nhân từng chữ số của num1 với num2 và cộng dồn kết quả vào biến tổng.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// Hàm hỗ trợ cộng hai chuỗi số lớn
string addStrings(string s1, string s2) {
    string res = "";
    int i = s1.length() - 1, j = s2.length() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry) {
        int d1 = (i >= 0) ? s1[i--] - '0' : 0;
        int d2 = (j >= 0) ? s2[j--] - '0' : 0;
        int sum = d1 + d2 + carry;
        res += (sum % 10) + '0';
        carry = sum / 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

string multiplyNaive(string num1, string num2) {
    if (num1 == "0" || num2 == "0") return "0";
    string finalResult = "0";
    for (int i = num1.length() - 1; i >= 0; i--) {
        string currentStep = "";
        int digit1 = num1[i] - '0';
        // Thêm các số 0 vào cuối dựa trên vị trí hàng thập phân
        for (int k = 0; k < (int)num1.length() - 1 - i; k++) currentStep += '0';
        
        string tempSum = "0";
        for (int j = 0; j < digit1; j++) {
            tempSum = addStrings(tempSum, num2);
        }
        if (tempSum != "0") {
            reverse(currentStep.begin(), currentStep.end());
            tempSum += currentStep;
            finalResult = addStrings(finalResult, tempSum);
        }
    }
    return finalResult;
}

Mặc dù logic này dễ hiểu nhưng hiệu suất rất kém do phải thực hiện quá nhiều phép cộng chuỗi, đặc biệt khi các chữ số trong num1 lớn (ví dụ chữ số '9').

Giải pháp 2: Tối ưu hóa bằng cách mô phỏng phép nhân tay (Optimal Approach)

Phương pháp này mô phỏng cách chúng ta nhân hai số trên giấy: nhân từng chữ số của số này với từng chữ số của số kia và đặt kết quả vào đúng vị trí tương ứng trong mảng kết quả.

Nếu num1 có độ dài $N$ và num2 có độ dài $M$, tích của chúng sẽ có độ dài tối đa là $N + M$. Ta sử dụng một mảng (hoặc vector) để lưu trữ các giá trị trung gian tại từng vị trí i + j + 1.

string multiply(string num1, string num2) {
    if (num1 == "0" || num2 == "0") return "0";
    
    int len1 = num1.size();
    int len2 = num2.size();
    // Mảng lưu kết quả trung gian có độ dài tối đa là tổng độ dài 2 chuỗi
    vector<int> positions(len1 + len2, 0);
    
    for (int i = len1 - 1; i >= 0; i--) {
        for (int j = len2 - 1; j >= 0; j--) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            int p1 = i + j;     // Vị trí hàng chục (nhớ)
            int p2 = i + j + 1; // Vị trí hàng đơn vị
            
            int sum = mul + positions[p2];
            positions[p2] = sum % 10;
            positions[p1] += sum / 10;
        }
    }
    
    string result = "";
    for (int p : positions) {
        // Bỏ qua các số 0 vô nghĩa ở đầu chuỗi
        if (!(result.empty() && p == 0)) {
            result += to_string(p);
        }
    }
    
    return result.empty() ? "0" : result;
}

Phân tích kỹ thuật

Để tối ưu bài toán này, chúng ta cần lưu ý các điểm sau:

1. Chuyển đổi ký tự: Kỹ thuật char - '0' là cách nhanh nhất để lấy giá trị số của một ký tự số trong bảng mã ASCII.
2. Vị trí chỉ số: Khi nhân chữ số tại num1[i] và num2[j], kết quả sẽ tác động lên hai vị trí liên tiếp trong mảng kết quả là i+j và i+j+1.
3. Xử lý số dư (Carry): Thay vì xử lý số dư ngay lập tức cho toàn bộ mảng, chúng ta có thể cộng dồn vào vị trí p2 và đẩy phần dư sang p1 trong mỗi bước lặp của vòng lặp con. Điều này giúp mã nguồn gọn gàng và tránh việc phải duyệt mảng nhiều lần.
4. Xóa số 0 thừa: Kết quả của mảng có thể chứa các số 0 ở đầu nếu tích không đạt độ dài tối đa $N+M$. Việc kiểm tra result.empty() trước khi thêm ký tự giúp loại bỏ chúng một cách tự nhiên.