#include <iostream>
#include <string>
using namespace std;

//multiply with one c
string multiply(string num, char c)
{
	if(num[0] == '0' || c == '0') return "0";
	
	string result(num.length(), '0');

	int carry = 0;
	int mul = c - '0';
	for (int i = num.length()-1; i >=0 ; --i)
	{
		int tmp = (num[i] - '0') * mul + carry;
		result[i] = tmp % 10 + '0';
		carry = tmp / 10;
	}

	if (carry > 0)result.insert(result.begin(), char('0' + carry));

	return result;
}
string multiply(string num1, string num2) 
{
	if(num1[0] == '0' || num2[0] == '0') return "0";
	
	//the maximum length of the multiplication result would at most equal to the sum of length of two numbers
	//and at least equal to the sum-1. 
	//Unless one of them is "0", then the result is length of 1.(but we have exclude it)
    string result(num1.length()+num2.length(), '0');
    string cache[10];//cache up the result so that we do not need to calcualte again
	
	for (int i = num2.length()-1; i>=0; --i)
	{
		int index = num2[i] - '0';
		if (cache[index].size() <= 0)
			cache[index] = multiply(num1, num2[i]);
		
		string& add = cache[index];
		
		//the k is shifted position in result for add up with
		int k = result.length() - (num2.length()-i);
		int j = add.length()-1;
		int carry = 0;
		while (j >= 0)
		{
			int tmp = (result[k] - '0') + (add[j] - '0') + carry;
			result[k] = tmp%10 + '0';
			carry = tmp / 10;
			--j, --k;
		}
	
		while (carry > 0)
		{
			int tmp = (result[k] - '0') + carry;
			result[k] = tmp%10 + '0';
			carry = tmp / 10;
			--k;
		}
	}
	
	if (result[0]=='0') result.erase(result.begin());
	
	return result;
}


int main(int argc, char** argv)
{
	cout << multiply("99", "988");
	return 0;
}