字符串是否包含问题（一）

    首先，这篇文章来自于July整理的PDF，我觉得很好，但是毕竟不是很方便阅读，所以，在这里整理下，以便随时可以温习。
    这个问题不是很难，但是，想到如此多的思路不是很容易，很佩服July的思维的活跃以及善于对知识的整理。
    下面，我们进入正题。
第一节、一个两个字符串是否包含的问题
    题目描述：
    假设有两个由各个字母组成的字符串longstring和shortstring，其中shortstring中的字符数目少一些。请以最快的速度短字符串shortstring中的字符是否都包含在长字符串longstring中？
    举例子如下。
    longstring：ABCDEFGHIJKLMNOPQRS
    shortstring: DCGSRQPOM
    答案是true。
    如果是以下两个字符串：
    longstring：ABCDEFGHIJKLMNOPQRS
    shortstring: DCGSRQPOMZ
    答案是false。
    
方法一：O(n*m)的轮询方法
    判断一个字符串是否在另一个字符串中，最直观的也是最简单的思路就是：针对第二个字符串中的每个字符串，一一与第一个字符串中的每个字符依次轮询比较，看是否在第二个字符串中。
    假设n是字符串longstring的长度，m是字符串shortstring的长度，那么此算法，需要O(n*m)次操作。

bool CompareString(string shortstr, string longstr)
{
    if(longstr.length() <=0 || shortstr.length() <= 0)
    {
        return false;
    }

    for(int i = 0; i < shortstr.length(); i++)
    {
        for(int j = 0; j < longstr.length(); j++)
        {
            if(shortstr[i] == longstr[j])
            {
                break;
            }
        }
        if(j >= longstr.length())
        {
            return false;
        }
    }

    return true;
}

    上述代码的时间复杂度为O(n*m)，显然。时间开销太大，需要寻找一种更好的方法。

方法二：O(mlogm) +O(nlogn) + O(m+n）
    一个稍微好点的方法就是对这两个字符串的字母进行排序，然后同时对这两个字符串依次轮询比较。两个字符串排序需要O(mlogm) +O(nlogn)次操作，之后进行线性扫描需要O(m+n)次操作。
    我们这里采用快速排序的方法，对其进行排序。

int Partion(string &str, int left, int right)
{
    char key = str[left];
    while(left < right)
    {
        while(left < right && str[right] >= key)
        {
            right--;
        }
        Swap(&str[left], &str[right]);

        while(left < right && str[left] <= key)
        {
            left++;
        }
        swap(str[left], str[right]);
    }

    return left;
}

void QuickSort(string &str, int first, int last)
{
    if(first < last)
    {
        int priot = Partion(str, first, last);
        QuickSort(str, first, priot - 1);
        QuickSort(str, priot + 1, last);
    }
}

//比较，上述排序O(m log m) + O(n log n)，加上下面的O(m+n)，
//时间复杂度总计为：O(mlogm)+O(nlogn)+O(m+n)。
//str1:长字符串        str2:短字符串
bool CompareString(string str1,string str2)
{
    int posOne = 0;
    int posTwo = 0;
    while (posTwo < str2.length() && posOne < str1.length())
    {
        while (str1[posOne] < str2[posTwo] && posOne < str1.length() - 1)
        {
            posOne++;
            //如果和str2相等，那就不能动。只有比str2小，才能动。
        }

        if (str1[posOne] != str2[posTwo])
            break;

        //posOne++;
        //归并的时候，str1[str1Pos] == str[str2Pos]的时候，只能str2Pos++,str1Pos不可以自增。

        posTwo++;
    }

    if (posTwo == str2.length())
    {
        return true;
    }
    else
    {
        return false;
    }
}

方法三：O(n+m)的计数排序方法
    此方法和上述思路相比，就是在排序的时候采用线性时间的计数排序方法，排序为O(m+n)，线性扫描O(m+n)，总的时间复杂度为O(n+m)。

//计数排序
void CountSort(string &str, string &longstr)
{
    int help[26];
    memset(help, 0, sizeof(help));

    for(int i = 0; i < str.length(); i++)
    {
        int temp = str[i] - 'A';
        help[temp]++;
    }

    //注意这里的26
    {
    for(i = 1; i < 26; i++)
        help[i] += help[i -1];
    }

    for(i = str.length() - 1; i >= 0; i--)
    {
        int temp = str[i] - 'A';
        int pos = help[temp] - 1;
        longstr[pos] = str[i];
        help[temp]--;
    }
}

bool CompareString(string longstr, string shortstr)
{
    int longlen = 0;
    int shortlen = 0;
    while(longlen < longstr.length() && shortlen < shortstr.length())
    {
        while(longstr[longlen] < shortstr[shortlen] && longlen < longstr.length())
        {
            longlen++;
        }
        //如果shortstr有重复的，去掉重复的
        while(shortstr[shortlen] == shortstr[shortlen + 1])
        {
            shortlen++;
        }
        if(shortstr[shortlen] != longstr[longlen])
        {
            break;
        }
        longlen++;
        shortlen++;
    }

    if(shortlen == shortstr.length())
    {
        return true;
    }
    else
    {
        return false;
    }
}

第二节、寻找线性时间解法

方法一：O(m+n)的Hash方法
    上述方案中，较好的方法就是先对字符串进行排序，然后进行线性扫描，总的时间复杂度已经优化到了O(n+m)，貌似已经到了极限，还有没有更好的方法呢？
    我们可以先对短字符串串进行轮询，然后轮询长的字符串，在Hash表中查询长字符串的每个字符，看是否可以找到？如果找不到，说明匹配不成功。
    或者，我们可以这样：
    1、hash[26]，先全部清零，然后扫描短字符串，若有则相应位置1；
    2、计算hash[26]中1的个数，设为m；
    3、扫描长字符串的每个字符a：若原来的hash[a]=1，则修改为hash[a]=0，并将m-1；若hash[a] =0，则不做处理；
    4、若m=0或扫描结束，退出循环

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

int main()
{
    string str1="ABCDEFGHLMNOPQRS";
    string str2="DCGSRQPOM";

    // 开辟一个辅助数组并清零
    int hash[26] = {0};

    // num为辅助数组中元素个数
    int num = 0;

    // 扫描短字符串
    for (int j = 0; j < str2.length(); j++)
    {
        // 将字符转换成对应辅助数组中的索引
        int index = str1[j] - 'A';

        // 如果辅助数组中该索引对应元素为0，则置1，且num++;
        if (hash[index] == 0)
        {
            hash[index] = 1;
            num++;
        }
    }

    // 扫描长字符串
    for (int k = 0; k < str1.length(); k++)
    {
        int index = str1[k] - 'A';

        // 如果辅助数组中该索引对应元素为1，则num--;为零的话，不作处理（不写语句）。
        if(hash[index] ==1)
        {
            hash[index] = 0;
            num--;
            if(num == 0) //m==0，即退出循环。
                break;
        }
    }

    // num为0说明长字符串包含短字符串内所有字符
    if (num == 0)
        cout << "true" << endl;
    else
        cout << "false" << endl;
    return 0;
}

方法二：O(m+n)的数组存储方法
    有两个字符串short_str和long_str。
    第一步：你标记short_str中有哪些字符，在store数组中标记为true。(store数组起一个映射的作用，如果有A，则将第1个单元标记true，如果有B,则将第2个单元标记true，... 如果有Z, 则将第26个单元标记true）
    第二步：遍历long_str，如果long_str中的字符包括short_str中的字符则将store数组中对应位置标记为false。(如果有 A，则将第1个单元标记false，如果有B,则将第2个单元标记false，... 如果有Z, 则将第26个单元标记false)，如果没有，则不作处理。
    第三步：此后，遍历store数组，如果所有的元素都是false，也就说明store_str中字符都包含在long_str内，输出true。否则，输出false。

    举个简单的例子好了，如abcd，abcdefg俩个字符串，
    1、先遍历短字符串abcd，在store数组中想对应的abcd的位置上的单元元素置为true，
    2、然后遍历abcdefg，在store数组中相应的abcd位置上，发现已经有了abcd，则前4个的单元元素都置为false，当我们已经遍历了4个元素，等于了短字符串abcd的4个数目，所以，满足条件，退出。
    （不然，继续遍历的话，我们会发现efg在store数组中没有元素，不作处理。最后，自然，就会发现store数组中的元素单元都是false的。）
    3、遍历store数组，发现所有的元素都已被置为false，所以程序输出true。

    其实，这个思路和上一节中， O（n+m）的Hash表的方法代码，原理是完全一致的，且本质上都采用的数组存储（hash表也是一个数组），但我并不认为此思路多此一举，所以仍然贴出来。ok，代码如下：

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

int main()
{
    char long_ch[]="ABCDEFGHLMNOPQRS";
    char short_ch[]="DEFGHXLMNOPQ";
    int i;
    bool store[58];
    memset(store,false,58);

    //前两个是遍历两个字符串, 后面一个是遍历数组
    for(i=0;i<sizeof(short_ch)-1;i++)
        store[short_ch[i]-65]=true;

    for(i=0;i<sizeof(long_ch)-1;i++)
    {
        if(store[long_ch[i]-65]!=false)
            store[long_ch[i]-65]=false;
    }
    for(i=0;i<58;i++)
    {
        if(store[i]!=false)
        {
            cout<<"short_ch is not in long_ch"<<endl;
            break;
        }
        if(i==57)
            cout<<"short_ch is in long_ch"<<endl;
    }

    return 0;
}

第三节、O(n)到O(m+n)的素数方法
    我想问的是，还有更好的方案么?
    你可能会这么想：O(n+m)是你能得到的最好的结果了，至少要对每个字母至少访问一次才能完成这项操作，而上一节最后的俩个方案是刚好是对每个字母只访问一次。

    ok，下面给出一个更好的方案：
    假设我们有一个一定个数的字母组成字串，我给每个字母分配一个素数，从2开始，往后类推。这样A将会是2，B将会是3，C将会是5，等等。现在我遍历第一个字串，把每个字母代表的素数相乘。你最终会得到一个很大的整数，对吧？
    然后——轮询第二个字符串，用每个字母除它。如果除的结果有余数，这说明有不匹配的字母。如果整个过程中没有余数，你应该知道它是第一个字串恰好的子集了。

    思路总结如下：
    1.定义最小的26个素数分别与字符'A'到'Z'对应。
    2.遍历长字符串，求得每个字符对应素数的乘积。
    3.遍历短字符串，判断乘积能否被短字符串中的字符对应的素数整除。
    4.输出结果。

    至此，如上所述，上述算法的时间复杂度为O(m+n)，时间复杂度最好的情况为O(n)（遍历短的字符串的第一个数，与长字符串素数的乘积相除，即出现余数，便可退出程序，返回false），n为长字串的长度，空间复杂度为O(1)。如你所见，我们已经优化到了最好的程度。

    不过，正如原文中所述：“现在我想告诉你 —— Guy的方案(不消说，我并不认为Guy是第一个想出这招的人)在算法上并不能说就比我的好。而且在实际操作中，你很可能仍会使用我的方案，因为它更通 用，无需跟麻烦的大型数字打交道。但从”巧妙水平“上讲，Guy提供的是一种更、更、更有趣的方案。”

#include <iostream>
#include <string>
#include "BigInt.h"
using namespace std;

// 素数数组
int primeNumber[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
                        61, 67, 71, 73, 79, 83, 89, 97, 101};

int main()
{
    string strOne = "ABCDEFGHLMNOPQRS";
    string strTwo = "DCGSRQPOM";

    // 这里需要用到大整数
    CBigInt product = 1; //大整数除法的代码，下头给出。

    // 遍历长字符串，得到每个字符对应素数的乘积
    for (int i = 0; i < strOne.length(); i++)
    {
        int index = strOne[i] - 'A';
        product = product * primeNumber[index];
    }

    // 遍历短字符串
    for (int j = 0; j < strTwo.length(); j++)
    {
        int index = strTwo[j] - 'A';

        // 如果余数不为0，说明不包括短字串中的字符，跳出循环
        if (product % primeNumber[index] != 0)
            break;
    }

    // 如果积能整除短字符串中所有字符则输出"true"，否则输出"false"。
    if (strTwo.length() == j)
        cout << "true" << endl;
    else
        cout << "false" << endl;
    return 0;
}

    上述程序待改进的地方：
    1.只考虑大些字符，如果考虑小写字符和数组的话，素数数组需要更多素数
    2.没有考虑重复的字符，可以加入判断重复字符的辅助数组。
    以下的大整数除法的代码，虽然与本题目无多大关系，但为了保证文章的完整性，我还是决定把它贴出来。

//copyright@ 2011/03/06 yansha
//实现大整数类
#include <string>
#include <vector>
#include <iostream>
using namespace std;

class CBigInt
{
public:
    // input
    friend istream& operator >> (istream &, CBigInt &);
    // output
    friend ostream& operator << (ostream &os, const CBigInt &value)
    {
        if (value.bigInt[0] == '-')
            os << value.bigInt;
        else
        {
            // 正数不输出符号
            os << value.bigInt.substr(1);
        }
        return os;
    }
    friend bool operator == (const CBigInt &, const CBigInt &);
    friend bool operator < (const CBigInt &lValue, const CBigInt &rValue)
    {
        if (lValue.bigInt[0] != rValue.bigInt[0])
        {
            // '+'ASCII码为43，'-'ASCII码为45
            return lValue.bigInt[0] > rValue.bigInt[0];
        }
        else
        {
            if (lValue.bigInt[0] == '+')
                return lValue.smaller(rValue.bigInt); // 正数的情况
            else
                return lValue.greater(rValue.bigInt); // 负数的情况
        }
    }

    friend bool operator > (const CBigInt &lValue, const CBigInt &rValue)
    {
        if (lValue.bigInt[0] != rValue.bigInt[0])
            return lValue.bigInt[0] < rValue.bigInt[0];
        else
        {
            if (lValue.bigInt[0] == '+')
                return lValue.greater(rValue.bigInt);
            else
                return lValue.smaller(rValue.bigInt);
        }
    }
    string bigInt;
public:
    CBigInt();
    CBigInt(int);
    CBigInt(const string &);
    CBigInt(const CBigInt &);
    CBigInt(const char *);
    CBigInt& operator = (const CBigInt &);
    CBigInt& operator += (const CBigInt &);
    CBigInt& operator -= (const CBigInt &);
    CBigInt& operator *= (const CBigInt &);
    CBigInt& operator /= (const CBigInt &);
    CBigInt& operator %= (const CBigInt &);

    // prefix increment
    CBigInt& operator ++ ();
    // prefix decrement
    CBigInt& operator -- ();
    // postfix increment
    CBigInt operator ++ (int);
    // postfix decrement
    CBigInt operator -- (int);
private:
    // unsigned +=
    void plus(const string &);
    // unsigned -=
    void minus(const string &);
    // unsigned ==
    bool equal(const string &) const;
    // unsigned <
    bool smaller(const string &) const;
    // unsigned >
    bool greater(const string &) const;
};

/************************************************************************/
/* 构造函数
/************************************************************************/
// 默认构造函数
inline CBigInt::CBigInt() : bigInt("+0")
{}

// 构造函数
inline CBigInt::CBigInt(const string &str) : bigInt(str)
{
    if (bigInt.size() > 0)
    {
        // 没有正负符号
        if (bigInt[0] != '+' && bigInt[0] != '-')
        {
            string::size_type i = 0;
            for (; i < bigInt.size() - 1 && bigInt[i] == '0'; i++);
            if (i > 0)
                bigInt.replace((string::size_type)0, i, "+");
            else
                bigInt.insert((string::size_type)0, 1, '+');
        }
        else
        {
            if (bigInt.size() == 1)
                bigInt = "+0";
            else
            {
                string::size_type j = 1;
                // 去掉多余的0
                for (; j < bigInt.size() - 1 && bigInt[j] == '0'; j++);
                if (j > 1)
                    bigInt.erase((string::size_type)1, j - 1);
                if (bigInt == "-0")
                    bigInt = "+0";
            }
        }
    }
    else
        bigInt = "+0";
}

// 复制构造函数
inline CBigInt::CBigInt(const CBigInt &value) : bigInt(value.bigInt)
{}

inline CBigInt::CBigInt(int num)
{
    if (num == 0)
        bigInt = "+0";
    else if (num > 0)
        bigInt = '+';
    else
    {
        bigInt = '-';
        num *= -1;
    }
    string temp = "";
    while (num != 0)
    {
        temp += num % 10 + '0';
        num = num / 10;
    }
    for (int i = temp.size() - 1; i >= 0; i--)
        bigInt += temp[i];
}

inline CBigInt::CBigInt(const char *str) : bigInt(str)
{
    if (bigInt.size() > 0)
    {
        if (bigInt[0] != '+' && bigInt[0] != '-')
        {
            string::size_type i = 0;
            // 去除多余的0
            for (; i < bigInt.size() - 1 && bigInt[i] == '0'; i++);
            if (i > 0)
                bigInt.replace((string::size_type)0, i, "+");
            else
                bigInt.insert((string::size_type)0, 1, '+');
        }
        else
        {
            if (bigInt.size() == 0)
                bigInt = "+0";
            else
            {
                string::size_type j = 1;
                for (; j < bigInt.size() - 1 && bigInt[j] == '0'; j++);
                if (j > 1)
                    bigInt.erase((string::size_type)1, j - 1);
                // 处理特殊情况“-0”
                if (bigInt == "-0")
                    bigInt = "+0";
            }
        }
    }
    else
        bigInt = "+0";
}

inline bool operator == (const CBigInt &lValue, const CBigInt &rValue)
{
    return lValue.bigInt == rValue.bigInt;
}

inline bool operator != (const CBigInt &lValue, const CBigInt &rValue)
{
    return !(lValue.bigInt == rValue.bigInt);
}

inline bool operator <= (const CBigInt &lValue, const CBigInt &rValue)
{
    return !(lValue > rValue);
}

inline bool operator >= (const CBigInt &lValue, const CBigInt &rValue)
{
    return !(lValue < rValue);
}

inline CBigInt& CBigInt::operator = (const CBigInt &value)
{
    bigInt = value.bigInt;
    return *this;
}

// unsigned ==
inline bool CBigInt::equal(const string &value) const
{
    return bigInt.substr(1) == value.substr(1);
}

// unsigned <
inline bool CBigInt::smaller(const string &value) const
{
    if (bigInt.size() == value.size())
        return bigInt.substr(1) < value.substr(1);
    else
        return bigInt.size() < value.size();
}

// unsigned >
inline bool CBigInt::greater(const string &value) const
{
    if (bigInt.size() == value.size())
        return bigInt.substr(1) > value.substr(1);
    else
        return bigInt.size() > value.size();
}

/************************************************************************/
/* 实现+,-,*,/运算
/************************************************************************/
void CBigInt::plus(const string &value)
{
    if (bigInt.size() < value.size())
        bigInt.insert((string::size_type)1, (value.size() - bigInt.size()), '0');
    string::size_type i = bigInt.size() - 1;
    string::size_type j = value.size() - 1;
    while (j > 1)
    {
        bigInt[i] += value[j] - '0';
        if (bigInt[i] > '9')
        {
            bigInt[i] -= 10;
            ++bigInt[i-1];
        }
        i--;
        j--;
    }

    // 最高位进位
    bigInt[i] += value[1] - '0';
    while (i > 1 && bigInt[i] > '9')
    {
        bigInt[i] -= 10;
        i--;
        ++bigInt[i];
    }

    if (bigInt[1] > '9')
    {
        bigInt[1] -= 10;
        bigInt.insert((string::size_type)1, 1, '1');
    }
}

void CBigInt::minus(const string &vlaue)
{
    string::size_type i = bigInt.size() - 1;
    string::size_type j = vlaue.size() - 1;
    while (j >= 1)
    {
        bigInt[i] -= vlaue[j] - '0';
        if (bigInt[i] < '0')
        {
            bigInt[i] += 10;
            --bigInt[i-1];
        }
        i--;
        j--;
    }

    // 向前借位
    while (i > 1 && bigInt[i] < '0')
    {
        bigInt[i] += 10;
        i--;
        --bigInt[i];
    }

    // 去除多余的0
    string::size_type k = 1;
    for (; k < bigInt.size() - 1 && bigInt[k] == '0'; k++);
    if (k > 1)
        bigInt.erase((string::size_type)1, k - 1);
}

CBigInt& CBigInt::operator += (const CBigInt &value)
{
    if (bigInt[0] == value.bigInt[0])
        plus(value.bigInt);
    else
    {
        // 互为相反数的情况
        if (equal(value.bigInt))
            bigInt = "+0";
        // 绝对值小于的情况
        else if (smaller(value.bigInt))
        {
            string temp = bigInt;
            bigInt = value.bigInt;
            minus(temp);
        }
        else
            minus(value.bigInt);
    }
    return *this;
}

CBigInt& CBigInt::operator -= (const CBigInt &value)
{
    // 处理过程与+=类似
    if (bigInt[0] == value.bigInt[0])
    {
        if (equal(value.bigInt))
            bigInt = "+0";
        else if (smaller(value.bigInt))
        {
            string temp = bigInt;
            bigInt = value.bigInt;
            minus(temp);
            if (bigInt[0] == '+')
                bigInt[0] = '-';
            else
                bigInt[0] = '+';
        }
        else
            minus(value.bigInt);
    }
    else
        plus(value.bigInt);
    return *this;
}

CBigInt operator + (const CBigInt &lValue, const CBigInt &rValue)
{
    CBigInt sum(lValue);
    sum += rValue;
    return sum;
}

CBigInt operator - (const CBigInt &lValue, const CBigInt &rValue)
{
    CBigInt diff(lValue);
    diff -= rValue;
    return diff;
}

// prefix increment
CBigInt& CBigInt::operator ++ ()
{
    string::size_type i = bigInt.size() - 1;
    if (bigInt[0] == '+')
    {
        ++bigInt[i];
        while (i > 1 && bigInt[i] > '9')
        {
            bigInt[i] -= 10;
            i--;
            ++bigInt[i];
        }

        if (bigInt[i] > '9')
        {
            bigInt[i] -= 10;
            bigInt.insert((string::size_type)1, 1, '1');
        }
    }
    else
    {
        --bigInt[i];
        while(i > 1 && bigInt[i] < '0')
        {
            bigInt[i] += 10;
            i--;
            --bigInt[i];
        }

        string::size_type j = 1;
        for (; j < bigInt.size() - 1 && bigInt[j] == '0'; j++);
        if (j > 1)
            bigInt.erase(1, j - 1);

        if (bigInt[1] == '0')
            bigInt[0] = '+';
    }
    return *this;
}

CBigInt& CBigInt::operator -- ()
{
    string::size_type i = bigInt.size() - 1;
    // 对正数和负数分别处理
    if (bigInt[0] == '+')
    {
        // 对0进行处理
        if (bigInt[1] == '0')
            bigInt = "-1";
        else
        {
            --bigInt[i];
            while (i > 1 && bigInt[i] < '0')
            {
                bigInt[i] += 10;
                i--;
                --bigInt[i];
            }

            string::size_type j = 1;
            for (; j < bigInt.size() - 1 && bigInt[j] == '0'; j++);
            if (j > 1)
                bigInt.erase(1, j - 1);
        }
    }
    else
    {
        ++bigInt[i];
        while (i > 1 && bigInt[i] > '9')
        {
            bigInt[i] -= 10;
            i--;
            ++bigInt[i];
        }

        if (bigInt[1] > '9')
        {
            bigInt[1] += 10;
            bigInt.insert((string::size_type)1, 1, '1');
        }
    }
    return *this;
}

// postfix increment
CBigInt CBigInt::operator ++ (int)
{
    CBigInt temp(*this);
    ++(*this);
    return temp;
}

// postfix decrement
CBigInt CBigInt::operator -- (int)
{
    CBigInt temp(*this);
    --(*this);
    return temp;
}

// 模拟笔算过程
CBigInt& CBigInt::operator *= (const CBigInt &value)
{
    // 乘数或被乘数有一方为0则返回结果0
    if (bigInt[1] == '0' || value.bigInt[1] == '0')
    {
        bigInt = "+0";
        return *this;
    }

    string::size_type sizeofMultiplicand = bigInt.size();
    string::size_type sizeofMultiplier = value.bigInt.size();
    vector<unsigned int> product(sizeofMultiplier + sizeofMultiplicand - 1);

    // 初始化
    for (string::size_type i = 1; i < sizeofMultiplicand; ++i)
        bigInt[i] -= '0';


    // 笔算乘法过程
    for (string::size_type j = sizeofMultiplier - 1; j > 0; --j)
    {
        if (value.bigInt[j] > '0')
        {
            for (string::size_type k = sizeofMultiplicand - 1; k > 0; --k)
                product[k+j] += bigInt[k] * (value.bigInt[j] - '0');
        }
    }

    // 处理符号
    if (bigInt[0] == value.bigInt[0])
        product[0] = '+';
    else
        product[0] = '-';

    vector<unsigned int>::size_type sizeofProduct = product.size();
    bigInt = string(sizeofProduct, '0');
    bigInt[0] = product[0];

    // 处理进位问题
    for (vector<unsigned int>::size_type n = sizeofProduct - 1; n > 1; --n)
    {
        product[n-1] += product[n] / 10;
        product[n] %= 10;
        bigInt[n] += product[n];
    }

    if (product[1] == 0)
        bigInt.erase(1, 1);
    else
        bigInt[1] += product[1];

    return *this;
}

// 重复做差法求商
CBigInt& CBigInt::operator /= (const CBigInt &value)
{
    // 除数为0
    if (value.bigInt == "+0")
    {
        bigInt = "*Error!";
        return *this;
    }

    // 被除数大于除数
    if (value.smaller(bigInt) == true)
    {
        string::size_type sizeofDividend = bigInt.size();
        string::size_type sizeofDivisor = value.bigInt.size();
        string answer(sizeofDividend, '0');

        // 符号处理
        if (bigInt[0] == value.bigInt[0])
            answer[0] = '+';
        else
            answer[0] = '-';

        string::size_type start = 1;
        string::size_type end = sizeofDivisor - 1;

        while (end < sizeofDividend)
        {
            // 试商过程，从高位到低位
            while (value.greater(bigInt.substr(start - 1, end - start + 2)) ==

false)
            {
                string::size_type j = end;
                // 减法过程
                for (string::size_type i = sizeofDivisor - 1; i > 0; i--, j--)
                {
                    bigInt[j] -= value.bigInt[i] - '0';
                    if (bigInt[j] < '0')
                    {
                        bigInt[j] += 10;
                        --bigInt[j-1];
                    }
                }

                // 商的相应位加1
                ++answer[end];

                // 以除数做边界去掉前缀0
                while (start <= end && bigInt[start] == '0')
                    ++start;
            }

            // 以被除数做边界去掉前缀0
            while (start < sizeofDividend && bigInt[start] == '0')
                ++start;

            // 如果end-start+1 < sizeofDivisor - 1,则进行补位
            if (end - start + 2 < sizeofDivisor)
                end = sizeofDivisor + start - 2;
            else
                ++end;
        }
        start = 1;
        for (; start < answer.size() - 1 && answer[start] == '0'; ++start);
        if (start > 1)
            answer.erase(1, start - 1);

        bigInt = answer;
    }
    // 绝对值相等的情况
    else if (value.equal(bigInt) == true)
    {
        string answer = "-1";
        if (bigInt[0] == value.bigInt[0])
            answer = "+1";
        bigInt = answer;
    }
    else
        bigInt = "+0";

    return *this;
}

// 求余，与上面去商过程基本一致
CBigInt& CBigInt::operator %= (const CBigInt &value)
{
    if (value.bigInt == "+0")
    {
        bigInt = "*Error!";
        return *this;
    }

    // 求余，余数为剩余bigInt值
    if (value.smaller(bigInt) == true)
    {
        string::size_type sizeofDivident = bigInt.size();
        string::size_type sizeofDivisor = value.bigInt.size();

        string::size_type start = 1;
        string::size_type end = sizeofDivisor - 1;
        while (end < sizeofDivident)
        {
            // 除数的值不大于被除数的值
            while (value.greater(bigInt.substr(start - 1, end - start + 2)) ==

false)
            {
                string::size_type j = end;
                for (string::size_type i = sizeofDivisor - 1; i > 0; --i, --j)
                {
                    bigInt[j] -= value.bigInt[i] - '0';
                    if (bigInt[j] < '0')
                    {
                        bigInt[j] += 10;
                        --bigInt[j-1];
                    }
                }

                while (start <= end && bigInt[start] == '0')
                    ++start;
            }

            while (start < sizeofDivident && bigInt[start] == '0')
                ++start;

            if (end - start + 2 < sizeofDivisor)
                end = sizeofDivisor + start - 2;
            else
                ++end;
        }

        start = 1;
        for (; start < sizeofDivident - 1 && bigInt[start] == '0'; start++);

        if (start > 1)
            bigInt.erase(1, start - 1);

        if (bigInt == "-0")
            bigInt[0] = '+';
    }
    else if (value.equal(bigInt))
        bigInt = "+0";
    return *this;
}

CBigInt operator * (const CBigInt &lValue, const CBigInt &rValue)
{
    CBigInt product(lValue);
    product *= rValue;
    return product;
}

CBigInt operator / (const CBigInt &lValue, const CBigInt &rValue)
{
    CBigInt quotient(lValue);
    quotient /= rValue;
    return quotient;
}

CBigInt operator % (const CBigInt &lValue, const CBigInt &rValue)
{
    CBigInt mod(lValue);
    mod %= rValue;
    return mod;
}

    说明：此次的判断字符串是否包含问题，来自一位外国网友提供的gofish、google面试题，这个题目出自此篇文章：http://www.aqee.net/2011/04/11/google-interviewing-story/，文章记录了整个面试的过程，比较有趣，值得一读。

    扩展 ：正如网友安逸所说：其实这个问题还可以转换为：a和b两个字符串，求b串包含a串的最小长度。包含指的就是b的字串包含a中每个字符。