Le problème consiste à multiplier deux nombres représentés par des chaînes de caractères et à retourner le résultat sous forme de chaîne. Les nombres peuvent être arbitrairement grands et sont non négatifs.

Une première idée serait de convertir chaque chaîne en entier, d'effectuer la multiplication, puis de reconvertir le résultat en chaîne. Cependant, cette approche échoue dès que les nombres dépassent la capacité des types natifs (par exemple, long long). Il faut donc simuler la multiplication posée, comme on l'apprend à l'école.

Approche par multiplication posée en base 10

On inverse les deux chaînes pour faciliter le calcul des retenues. On utilise un tableau d'entiers pour stocker les résultats intermédiaires, puis on normalise les retenues. Enfin, on supprime les zéros superflus en tête.

#include <string>
#include <vector>
#include <algorithm>

std::string multiplier(const std::string& a, const std::string& b) {
    if (a == "0" || b == "0") return "0";
    int la = a.size(), lb = b.size();
    std::vector<int> produit(la + lb, 0);

    // Multiplication sans retenue
    for (int i = 0; i < la; ++i) {
        for (int j = 0; j < lb; ++j) {
            produit[i + j] += (a[la - 1 - i] - '0') * (b[lb - 1 - j] - '0');
        }
    }

    // Gestion des retenues
    int retenue = 0;
    for (int i = 0; i < la + lb; ++i) {
        int total = produit[i] + retenue;
        produit[i] = total % 10;
        retenue = total / 10;
    }

    // Construction de la chaîne résultat
    std::string res;
    for (int i = la + lb - 1; i >= 0; --i) {
        if (!(res.empty() && produit[i] == 0)) {
            res.push_back('0' + produit[i]);
        }
    }
    return res.empty() ? "0" : res;
}

Version optimisée avec retenue intégrée

On peut intégrer la retenue directement dans la boucle de multiplication pour éviter un second parcours :

std::string multiplier2(const std::string& a, const std::string& b) {
    int la = a.size(), lb = b.size();
    std::string result(la + lb, '0');

    for (int i = la - 1; i >= 0; --i) {
        int retenue = 0;
        for (int j = lb - 1; j >= 0; --j) {
            int tmp = (result[i + j + 1] - '0') + (a[i] - '0') * (b[j] - '0') + retenue;
            result[i + j + 1] = (tmp % 10) + '0';
            retenue = tmp / 10;
        }
        result[i] += retenue;
    }

    size_t debut = result.find_first_not_of('0');
    if (debut != std::string::npos) return result.substr(debut);
    return "0";
}

Base 1 000 000 000 pour de meilleures performances

Au lieu de travailler en base 10, on peut regrouper les chiffres en paquets de 9 (car 10⁹ tient dans un entier 32 bits). Cela réduit le nombre d'opérations et améliore le temps d'exécution.

#include <cstdint>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>

using u32 = uint32_t;
using u64 = uint64_t;

void versBase1e9(const std::string& s, std::vector<u32>& out) {
    u32 valeur = 0, facteur = 1;
    int i = s.size() - 1;
    while (i >= 0) {
        valeur += (s[i] - '0') * facteur;
        if (facteur == 100000000) {
            out.push_back(valeur);
            valeur = 0;
            facteur = 1;
        } else {
            facteur *= 10;
        }
        --i;
    }
    if (facteur != 1) out.push_back(valeur);
}

std::string depuisBase1e9(const std::vector<u32>& num) {
    if (num.empty()) return "0";
    std::ostringstream oss;
    for (int i = num.size() - 1; i >= 0; --i) {
        if (i != (int)num.size() - 1)
            oss << std::setw(9) << std::setfill('0');
        oss << num[i];
    }
    return oss.str();
}

std::string multiplierGrand(const std::string& a, const std::string& b) {
    if (a == "0" || b == "0") return "0";
    std::vector<u32> da, db;
    versBase1e9(a, da);
    versBase1e9(b, db);

    std::vector<u32> res;
    for (size_t j = 0; j < db.size(); ++j) {
        u32 nb = db[j];
        u32 retenue = 0;
        size_t pos = j;
        for (size_t i = 0; i < da.size(); ++i) {
            if (pos >= res.size()) res.push_back(0);
            u64 mul = (u64)nb * da[i] + res[pos] + retenue;
            res[pos] = mul % 1000000000;
            retenue = mul / 1000000000;
            ++pos;
        }
        if (retenue) {
            if (pos >= res.size()) res.push_back(0);
            res[pos] = retenue;
        }
    }
    return depuisBase1e9(res);
}

Ces trois solutions illustrent différentes façons de réaliser la multiplication de grands entiers sans recourir à des bibliohtèques externes. La version en base 1e9 offre le meilelur compromis entre simplicité et rapidité, tandis que les versions en base 10 sont plus faciles à comprendre.