Multiply Strings ใน C++ - คูณสตริงตัวเลขขนาดใหญ่

สมมติว่าเรามีตัวเลขสองตัวเป็นสตริง เราต้องคูณพวกมันและคืนผลลัพธ์เป็นสตริงเช่นกัน ตัวอย่าง "26" และ "12" ผลลัพธ์ "312"

ขั้นตอนการทำงาน (Grade School Multiplication)

1. รับอาร์กิวเมนต์สองตัว x และ y หมายถึง x หาร y
2. ถ้า x < -Infinity และ y = 1 คืน infinity
3. a := |x|, b := |y|, ans := 0
4. วนลูป while a - b >= 0:
   • p := 0
   • วนลูป while a - (b << (p + 1)) >= 0: p := p + 1
   • a := a - (b << p)
   • ans := ans + (1 << p)
5. ถ้า x > 0 และ y > 0 คืน ans มิฉะนั้นคืน -ans

ตัวอย่างโค้ด (C++)

#include 
using namespace std;

class Solution {
public:
    string multiply(string num1, string num2);
};

string Solution::multiply(string nums1, string nums2) {
    int n = nums1.size();
    int m = nums2.size();
    string ans(n + m, '0');
    for(int i = n - 1; i >= 0; i--){
        for(int j = m - 1; j >= 0; j--){
            int p = (nums1[i] - '0') * (nums2[j] - '0') + (ans[i + j + 1] - '0');
            ans[i+j+1] = p % 10 + '0';
            ans[i+j] += p / 10;
        }
    }
    for(int i = 0; i < m + n; i++){
        if(ans[i] != '0') return ans.substr(i);
    }
    return "0";
}

int main(){
    Solution ob;
    cout << ob.multiply("28", "25");
}

อินพุต

"26" "12"

เอาต์พุต

"312"