Chinaunix首页 | 论坛 | 博客

快乐的小牛joepayne.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

joepayne

  • 博客访问： 628731
  • 博文数量： 108
  • 博客积分： 46
  • 博客等级： 民兵
  • 技术积分： 1279
  • 用 户 组： 普通用户
  • 注册时间： 2012-08-16 11:36
个人简介

坐井以观天

文章分类

全部博文（108）

文章存档

2014年（13）

2013年（90）

2012年（6）

我的朋友
最近访客
推荐博文
相关博文
字符串是否包含问题（一）

分类： C/C++

2013-06-27 17:41:49

原文地址：字符串是否包含问题（一） 作者：梦醒潇湘love


    首先，这篇文章来自于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)次操作。

  1. bool CompareString(string shortstr, string longstr)
  2. {
  3.     if(longstr.length() <=0 || shortstr.length() <= 0)
  4.     {
  5.         return false;
  6.     }
  7.     
  8.     for(int i = 0; i < shortstr.length(); i++)
  9.     {
  10.         for(int j = 0; j < longstr.length(); j++)
  11.         {
  12.             if(shortstr[i] == longstr[j])
  13.             {
  14.                 break;
  15.             }
  16.         }
  17.         if(j >= longstr.length())
  18.         {
  19.             return false;
  20.         }
  21.     }

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

方法二：O(mlogm) +O(nlogn) + O(m+n）
    一个稍微好点的方法就是对这两个字符串的字母进行排序，然后同时对这两个字符串依次轮询比较。两个字符串排序需要O(mlogm) +O(nlogn)次操作，之后进行线性扫描需要O(m+n)次操作。
    我们这里采用快速排序的方法，对其进行排序。
  1. int Partion(string &str, int left, int right)
  2. {
  3.     char key = str[left];
  4.     while(left < right)
  5.     {
  6.         while(left < right && str[right] >= key)
  7.         {
  8.             right--;
  9.         }
  10.         Swap(&str[left], &str[right]);
  11.         
  12.         while(left < right && str[left] <= key)
  13.         {
  14.             left++;
  15.         }
  16.         swap(str[left], str[right]);
  17.     }
  18.     
  19.     return left;
  20. }

  22. void QuickSort(string &str, int first, int last)
  23. {
  24.     if(first < last)
  25.     {
  26.         int priot = Partion(str, first, last);
  27.         QuickSort(str, first, priot - 1);
  28.         QuickSort(str, priot + 1, last);
  29.     }
  30. }

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

  47.         if (str1[posOne] != str2[posTwo])
  48.             break;
  49.         
  50.         //posOne++;
  51.         //归并的时候，str1[str1Pos] == str[str2Pos]的时候，只能str2Pos++,str1Pos不可以自增。
  52.         
  53.         posTwo++;
  54.     }
  55.     
  56.     if (posTwo == str2.length())
  57.     {
  58.         return true;
  59.     }
  60.     else
  61.     {
  62.         return false;
  63.     }
  64. }
方法三：O(n+m)的计数排序方法
    此方法和上述思路相比，就是在排序的时候采用线性时间的计数排序方法，排序为O(m+n)，线性扫描O(m+n)，总的时间复杂度为O(n+m)。

  1. //计数排序
  2. void CountSort(string &str, string &longstr)
  3. {
  4.     int help[26];
  5.     memset(help, 0, sizeof(help));
  6.     
  7.     for(int i = 0; i < str.length(); i++)
  8.     {
  9.         int temp = str[i] - 'A';
  10.         help[temp]++;
  11.     }

  13.     //注意这里的26
  14.     {
  15.     for(i = 1; i < 26; i++)
  16.         help[i] += help[i -1];
  17.     }

  19.     for(i = str.length() - 1; i >= 0; i--)
  20.     {
  21.         int temp = str[i] - 'A';
  22.         int pos = help[temp] - 1;
  23.         longstr[pos] = str[i];
  24.         help[temp]--;
  25.     }
  26. }

  28. bool CompareString(string longstr, string shortstr)
  29. {
  30.     int longlen = 0;
  31.     int shortlen = 0;
  32.     while(longlen < longstr.length() && shortlen < shortstr.length())
  33.     {
  34.         while(longstr[longlen] < shortstr[shortlen] && longlen < longstr.length())
  35.         {
  36.             longlen++;
  37.         }
  38.         //如果shortstr有重复的，去掉重复的
  39.         while(shortstr[shortlen] == shortstr[shortlen + 1])
  40.         {
  41.             shortlen++;
  42.         }
  43.         if(shortstr[shortlen] != longstr[longlen])
  44.         {
  45.             break;
  46.         }
  47.         longlen++;
  48.         shortlen++;
  49.     }

  51.     if(shortlen == shortstr.length())
  52.     {
  53.         return true;
  54.     }
  55.     else
  56.     {
  57.         return false;
  58.     }
  59. }
第二节、寻找线性时间解法

方法一：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或扫描结束，退出循环

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.   
  5. int main()
  6. {
  7.     string str1="ABCDEFGHLMNOPQRS";
  8.     string str2="DCGSRQPOM";
  9.   
  10.     // 开辟一个辅助数组并清零
  11.     int hash[26] = {0};
  12.   
  13.     // num为辅助数组中元素个数
  14.     int num = 0;
  15.   
  16.     // 扫描短字符串
  17.     for (int j = 0; j < str2.length(); j++)
  18.     {
  19.         // 将字符转换成对应辅助数组中的索引
  20.         int index = str1[j] - 'A';
  21.   
  22.         // 如果辅助数组中该索引对应元素为0，则置1，且num++;
  23.         if (hash[index] == 0)
  24.         {
  25.             hash[index] = 1;
  26.             num++;
  27.         }
  28.     }
  29.   
  30.     // 扫描长字符串
  31.     for (int k = 0; k < str1.length(); k++)
  32.     {
  33.         int index = str1[k] - 'A';
  34.   
  35.         // 如果辅助数组中该索引对应元素为1，则num--;为零的话，不作处理（不写语句）。
  36.         if(hash[index] ==1)
  37.         {
  38.             hash[index] = 0;
  39.             num--;
  40.             if(num == 0) //m==0，即退出循环。
  41.                 break;
  42.         }
  43.     }
  44.   
  45.     // num为0说明长字符串包含短字符串内所有字符
  46.     if (num == 0)
  47.         cout << "true" << endl;
  48.     else
  49.         cout << "false" << endl;
  50.     return 0;
  51. }

方法二：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，代码如下：
  1. #include<iostream>
  2. #include<string.h>
  3. using namespace std;
  4.   
  5. int main()
  6. {
  7.     char long_ch[]="ABCDEFGHLMNOPQRS";
  8.     char short_ch[]="DEFGHXLMNOPQ";
  9.     int i;
  10.     bool store[58];
  11.     memset(store,false,58);
  12.       
  13.     //前两个是遍历两个字符串, 后面一个是遍历数组
  14.     for(i=0;i<sizeof(short_ch)-1;i++)
  15.         store[short_ch[i]-65]=true;
  16.       
  17.     for(i=0;i<sizeof(long_ch)-1;i++)
  18.     {
  19.         if(store[long_ch[i]-65]!=false)
  20.             store[long_ch[i]-65]=false;
  21.     }
  22.     for(i=0;i<58;i++)
  23.     {
  24.         if(store[i]!=false)
  25.         {
  26.             cout<<"short_ch is not in long_ch"<<endl;
  27.             break;
  28.         }
  29.         if(i==57)
  30.             cout<<"short_ch is in long_ch"<<endl;
  31.     }
  32.       
  33.     return 0;
  34. }

第三节、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提供的是一种更、更、更有趣的方案。”

  1. #include <iostream>
  2. #include <string>
  3. #include "BigInt.h"
  4. using namespace std;
  5.   
  6. // 素数数组
  7. int primeNumber[26] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
  8.                         61, 67, 71, 73, 79, 83, 89, 97, 101};
  9.   
  10. int main()
  11. {
  12.     string strOne = "ABCDEFGHLMNOPQRS";
  13.     string strTwo = "DCGSRQPOM";
  14.   
  15.     // 这里需要用到大整数
  16.     CBigInt product = 1; //大整数除法的代码，下头给出。
  17.   
  18.     // 遍历长字符串，得到每个字符对应素数的乘积
  19.     for (int i = 0; i < strOne.length(); i++)
  20.     {
  21.         int index = strOne[i] - 'A';
  22.         product = product * primeNumber[index];
  23.     }
  24.   
  25.     // 遍历短字符串
  26.     for (int j = 0; j < strTwo.length(); j++)
  27.     {
  28.         int index = strTwo[j] - 'A';
  29.   
  30.         // 如果余数不为0，说明不包括短字串中的字符，跳出循环
  31.         if (product % primeNumber[index] != 0)
  32.             break;
  33.     }
  34.   
  35.     // 如果积能整除短字符串中所有字符则输出"true"，否则输出"false"。
  36.     if (strTwo.length() == j)
  37.         cout << "true" << endl;
  38.     else
  39.         cout << "false" << endl;
  40.     return 0;
  41. }
    上述程序待改进的地方：
    1.只考虑大些字符，如果考虑小写字符和数组的话，素数数组需要更多素数
    2.没有考虑重复的字符，可以加入判断重复字符的辅助数组。
    以下的大整数除法的代码，虽然与本题目无多大关系，但为了保证文章的完整性，我还是决定把它贴出来。

点击(此处)折叠或打开

  1. //copyright@ 2011/03/06 yansha
  2. //实现大整数类
  3. #include <string>
  4. #include <vector>
  5. #include <iostream>
  6. using namespace std;
  7.   
  8. class CBigInt
  9. {
  10. public:
  11.     // input
  12.     friend istream& operator >> (istream &, CBigInt &);
  13.     // output
  14.     friend ostream& operator << (ostream &os, const CBigInt &value)
  15.     {
  16.         if (value.bigInt[0] == '-')
  17.             os << value.bigInt;
  18.         else
  19.         {
  20.             // 正数不输出符号
  21.             os << value.bigInt.substr(1);
  22.         }
  23.         return os;
  24.     }
  25.     friend bool operator == (const CBigInt &, const CBigInt &);
  26.     friend bool operator < (const CBigInt &lValue, const CBigInt &rValue)
  27.     {
  28.         if (lValue.bigInt[0] != rValue.bigInt[0])
  29.         {
  30.             // '+'ASCII码为43，'-'ASCII码为45
  31.             return lValue.bigInt[0] > rValue.bigInt[0];
  32.         }
  33.         else
  34.         {
  35.             if (lValue.bigInt[0] == '+')
  36.                 return lValue.smaller(rValue.bigInt); // 正数的情况
  37.             else
  38.                 return lValue.greater(rValue.bigInt); // 负数的情况
  39.         }
  40.     }
  41.       
  42.     friend bool operator > (const CBigInt &lValue, const CBigInt &rValue)
  43.     {
  44.         if (lValue.bigInt[0] != rValue.bigInt[0])
  45.             return lValue.bigInt[0] < rValue.bigInt[0];
  46.         else
  47.         {
  48.             if (lValue.bigInt[0] == '+')
  49.                 return lValue.greater(rValue.bigInt);
  50.             else
  51.                 return lValue.smaller(rValue.bigInt);
  52.         }
  53.     }
  54.     string bigInt;
  55. public:
  56.     CBigInt();
  57.     CBigInt(int);
  58.     CBigInt(const string &);
  59.     CBigInt(const CBigInt &);
  60.     CBigInt(const char *);
  61.     CBigInt& operator = (const CBigInt &);
  62.     CBigInt& operator += (const CBigInt &);
  63.     CBigInt& operator -= (const CBigInt &);
  64.     CBigInt& operator *= (const CBigInt &);
  65.     CBigInt& operator /= (const CBigInt &);
  66.     CBigInt& operator %= (const CBigInt &);
  67.       
  68.     // prefix increment
  69.     CBigInt& operator ++ ();
  70.     // prefix decrement
  71.     CBigInt& operator -- ();
  72.     // postfix increment
  73.     CBigInt operator ++ (int);
  74.     // postfix decrement
  75.     CBigInt operator -- (int);
  76. private:
  77.     // unsigned +=
  78.     void plus(const string &);
  79.     // unsigned -=
  80.     void minus(const string &);
  81.     // unsigned ==
  82.     bool equal(const string &) const;
  83.     // unsigned <
  84.     bool smaller(const string &) const;
  85.     // unsigned >
  86.     bool greater(const string &) const;
  87. };
  88.   
  89. /************************************************************************/
  90. /* 构造函数
  91. /************************************************************************/
  92. // 默认构造函数
  93. inline CBigInt::CBigInt() : bigInt("+0")
  94. {}
  95.   
  96. // 构造函数
  97. inline CBigInt::CBigInt(const string &str) : bigInt(str)
  98. {
  99.     if (bigInt.size() > 0)
  100.     {
  101.         // 没有正负符号
  102.         if (bigInt[0] != '+' && bigInt[0] != '-')
  103.         {
  104.             string::size_type i = 0;
  105.             for (; i < bigInt.size() - 1 && bigInt[i] == '0'; i++);
  106.             if (i > 0)
  107.                 bigInt.replace((string::size_type)0, i, "+");
  108.             else
  109.                 bigInt.insert((string::size_type)0, 1, '+');
  110.         }
  111.         else
  112.         {
  113.             if (bigInt.size() == 1)
  114.                 bigInt = "+0";
  115.             else
  116.             {
  117.                 string::size_type j = 1;
  118.                 // 去掉多余的0
  119.                 for (; j < bigInt.size() - 1 && bigInt[j] == '0'; j++);
  120.                 if (j > 1)
  121.                     bigInt.erase((string::size_type)1, j - 1);
  122.                 if (bigInt == "-0")
  123.                     bigInt = "+0";
  124.             }
  125.         }
  126.     }
  127.     else
  128.         bigInt = "+0";
  129. }
  130.   
  131. // 复制构造函数
  132. inline CBigInt::CBigInt(const CBigInt &value) : bigInt(value.bigInt)
  133. {}
  134.   
  135. inline CBigInt::CBigInt(int num)
  136. {
  137.     if (num == 0)
  138.         bigInt = "+0";
  139.     else if (num > 0)
  140.         bigInt = '+';
  141.     else
  142.     {
  143.         bigInt = '-';
  144.         num *= -1;
  145.     }
  146.     string temp = "";
  147.     while (num != 0)
  148.     {
  149.         temp += num % 10 + '0';
  150.         num = num / 10;
  151.     }
  152.     for (int i = temp.size() - 1; i >= 0; i--)
  153.         bigInt += temp[i];
  154. }
  155.   
  156. inline CBigInt::CBigInt(const char *str) : bigInt(str)
  157. {
  158.     if (bigInt.size() > 0)
  159.     {
  160.         if (bigInt[0] != '+' && bigInt[0] != '-')
  161.         {
  162.             string::size_type i = 0;
  163.             // 去除多余的0
  164.             for (; i < bigInt.size() - 1 && bigInt[i] == '0'; i++);
  165.             if (i > 0)
  166.                 bigInt.replace((string::size_type)0, i, "+");
  167.             else
  168.                 bigInt.insert((string::size_type)0, 1, '+');
  169.         }
  170.         else
  171.         {
  172.             if (bigInt.size() == 0)
  173.                 bigInt = "+0";
  174.             else
  175.             {
  176.                 string::size_type j = 1;
  177.                 for (; j < bigInt.size() - 1 && bigInt[j] == '0'; j++);
  178.                 if (j > 1)
  179.                     bigInt.erase((string::size_type)1, j - 1);
  180.                 // 处理特殊情况“-0”
  181.                 if (bigInt == "-0")
  182.                     bigInt = "+0";
  183.             }
  184.         }
  185.     }
  186.     else
  187.         bigInt = "+0";
  188. }
  189.   
  190. inline bool operator == (const CBigInt &lValue, const CBigInt &rValue)
  191. {
  192.     return lValue.bigInt == rValue.bigInt;
  193. }
  194.   
  195. inline bool operator != (const CBigInt &lValue, const CBigInt &rValue)
  196. {
  197.     return !(lValue.bigInt == rValue.bigInt);
  198. }
  199.   
  200. inline bool operator <= (const CBigInt &lValue, const CBigInt &rValue)
  201. {
  202.     return !(lValue > rValue);
  203. }
  204.   
  205. inline bool operator >= (const CBigInt &lValue, const CBigInt &rValue)
  206. {
  207.     return !(lValue < rValue);
  208. }
  209.   
  210. inline CBigInt& CBigInt::operator = (const CBigInt &value)
  211. {
  212.     bigInt = value.bigInt;
  213.     return *this;
  214. }
  215.   
  216. // unsigned ==
  217. inline bool CBigInt::equal(const string &value) const
  218. {
  219.     return bigInt.substr(1) == value.substr(1);
  220. }
  221.   
  222. // unsigned <
  223. inline bool CBigInt::smaller(const string &value) const
  224. {
  225.     if (bigInt.size() == value.size())
  226.         return bigInt.substr(1) < value.substr(1);
  227.     else
  228.         return bigInt.size() < value.size();
  229. }
  230.   
  231. // unsigned >
  232. inline bool CBigInt::greater(const string &value) const
  233. {
  234.     if (bigInt.size() == value.size())
  235.         return bigInt.substr(1) > value.substr(1);
  236.     else
  237.         return bigInt.size() > value.size();
  238. }
  239.   
  240. /************************************************************************/
  241. /* 实现+,-,*,/运算
  242. /************************************************************************/
  243. void CBigInt::plus(const string &value)
  244. {
  245.     if (bigInt.size() < value.size())
  246.         bigInt.insert((string::size_type)1, (value.size() - bigInt.size()), '0');
  247.     string::size_type i = bigInt.size() - 1;
  248.     string::size_type j = value.size() - 1;
  249.     while (j > 1)
  250.     {
  251.         bigInt[i] += value[j] - '0';
  252.         if (bigInt[i] > '9')
  253.         {
  254.             bigInt[i] -= 10;
  255.             ++bigInt[i-1];
  256.         }
  257.         i--;
  258.         j--;
  259.     }
  260.       
  261.     // 最高位进位
  262.     bigInt[i] += value[1] - '0';
  263.     while (i > 1 && bigInt[i] > '9')
  264.     {
  265.         bigInt[i] -= 10;
  266.         i--;
  267.         ++bigInt[i];
  268.     }
  269.       
  270.     if (bigInt[1] > '9')
  271.     {
  272.         bigInt[1] -= 10;
  273.         bigInt.insert((string::size_type)1, 1, '1');
  274.     }
  275. }
  276.   
  277. void CBigInt::minus(const string &vlaue)
  278. {
  279.     string::size_type i = bigInt.size() - 1;
  280.     string::size_type j = vlaue.size() - 1;
  281.     while (j >= 1)
  282.     {
  283.         bigInt[i] -= vlaue[j] - '0';
  284.         if (bigInt[i] < '0')
  285.         {
  286.             bigInt[i] += 10;
  287.             --bigInt[i-1];
  288.         }
  289.         i--;
  290.         j--;
  291.     }
  292.       
  293.     // 向前借位
  294.     while (i > 1 && bigInt[i] < '0')
  295.     {
  296.         bigInt[i] += 10;
  297.         i--;
  298.         --bigInt[i];
  299.     }
  300.       
  301.     // 去除多余的0
  302.     string::size_type k = 1;
  303.     for (; k < bigInt.size() - 1 && bigInt[k] == '0'; k++);
  304.     if (k > 1)
  305.         bigInt.erase((string::size_type)1, k - 1);
  306. }
  307.   
  308. CBigInt& CBigInt::operator += (const CBigInt &value)
  309. {
  310.     if (bigInt[0] == value.bigInt[0])
  311.         plus(value.bigInt);
  312.     else
  313.     {
  314.         // 互为相反数的情况
  315.         if (equal(value.bigInt))
  316.             bigInt = "+0";
  317.         // 绝对值小于的情况
  318.         else if (smaller(value.bigInt))
  319.         {
  320.             string temp = bigInt;
  321.             bigInt = value.bigInt;
  322.             minus(temp);
  323.         }
  324.         else
  325.             minus(value.bigInt);
  326.     }
  327.     return *this;
  328. }
  329.   
  330. CBigInt& CBigInt::operator -= (const CBigInt &value)
  331. {
  332.     // 处理过程与+=类似
  333.     if (bigInt[0] == value.bigInt[0])
  334.     {
  335.         if (equal(value.bigInt))
  336.             bigInt = "+0";
  337.         else if (smaller(value.bigInt))
  338.         {
  339.             string temp = bigInt;
  340.             bigInt = value.bigInt;
  341.             minus(temp);
  342.             if (bigInt[0] == '+')
  343.                 bigInt[0] = '-';
  344.             else
  345.                 bigInt[0] = '+';
  346.         }
  347.         else
  348.             minus(value.bigInt);
  349.     }
  350.     else
  351.         plus(value.bigInt);
  352.     return *this;
  353. }
  354.   
  355. CBigInt operator + (const CBigInt &lValue, const CBigInt &rValue)
  356. {
  357.     CBigInt sum(lValue);
  358.     sum += rValue;
  359.     return sum;
  360. }
  361.   
  362. CBigInt operator - (const CBigInt &lValue, const CBigInt &rValue)
  363. {
  364.     CBigInt diff(lValue);
  365.     diff -= rValue;
  366.     return diff;
  367. }
  368.   
  369. // prefix increment
  370. CBigInt& CBigInt::operator ++ ()
  371. {
  372.     string::size_type i = bigInt.size() - 1;
  373.     if (bigInt[0] == '+')
  374.     {
  375.         ++bigInt[i];
  376.         while (i > 1 && bigInt[i] > '9')
  377.         {
  378.             bigInt[i] -= 10;
  379.             i--;
  380.             ++bigInt[i];
  381.         }
  382.           
  383.         if (bigInt[i] > '9')
  384.         {
  385.             bigInt[i] -= 10;
  386.             bigInt.insert((string::size_type)1, 1, '1');
  387.         }
  388.     }
  389.     else
  390.     {
  391.         --bigInt[i];
  392.         while(i > 1 && bigInt[i] < '0')
  393.         {
  394.             bigInt[i] += 10;
  395.             i--;
  396.             --bigInt[i];
  397.         }
  398.           
  399.         string::size_type j = 1;
  400.         for (; j < bigInt.size() - 1 && bigInt[j] == '0'; j++);
  401.         if (j > 1)
  402.             bigInt.erase(1, j - 1);
  403.           
  404.         if (bigInt[1] == '0')
  405.             bigInt[0] = '+';
  406.     }
  407.     return *this;
  408. }
  409.   
  410. CBigInt& CBigInt::operator -- ()
  411. {
  412.     string::size_type i = bigInt.size() - 1;
  413.     // 对正数和负数分别处理
  414.     if (bigInt[0] == '+')
  415.     {
  416.         // 对0进行处理
  417.         if (bigInt[1] == '0')
  418.             bigInt = "-1";
  419.         else
  420.         {
  421.             --bigInt[i];
  422.             while (i > 1 && bigInt[i] < '0')
  423.             {
  424.                 bigInt[i] += 10;
  425.                 i--;
  426.                 --bigInt[i];
  427.             }
  428.               
  429.             string::size_type j = 1;
  430.             for (; j < bigInt.size() - 1 && bigInt[j] == '0'; j++);
  431.             if (j > 1)
  432.                 bigInt.erase(1, j - 1);
  433.         }
  434.     }
  435.     else
  436.     {
  437.         ++bigInt[i];
  438.         while (i > 1 && bigInt[i] > '9')
  439.         {
  440.             bigInt[i] -= 10;
  441.             i--;
  442.             ++bigInt[i];
  443.         }
  444.           
  445.         if (bigInt[1] > '9')
  446.         {
  447.             bigInt[1] += 10;
  448.             bigInt.insert((string::size_type)1, 1, '1');
  449.         }
  450.     }
  451.     return *this;
  452. }
  453.   
  454. // postfix increment
  455. CBigInt CBigInt::operator ++ (int)
  456. {
  457.     CBigInt temp(*this);
  458.     ++(*this);
  459.     return temp;
  460. }
  461.   
  462. // postfix decrement
  463. CBigInt CBigInt::operator -- (int)
  464. {
  465.     CBigInt temp(*this);
  466.     --(*this);
  467.     return temp;
  468. }
  469.   
  470. // 模拟笔算过程
  471. CBigInt& CBigInt::operator *= (const CBigInt &value)
  472. {
  473.     // 乘数或被乘数有一方为0则返回结果0
  474.     if (bigInt[1] == '0' || value.bigInt[1] == '0')
  475.     {
  476.         bigInt = "+0";
  477.         return *this;
  478.     }
  479.       
  480.     string::size_type sizeofMultiplicand = bigInt.size();
  481.     string::size_type sizeofMultiplier = value.bigInt.size();
  482.     vector<unsigned int> product(sizeofMultiplier + sizeofMultiplicand - 1);
  483.       
  484.     // 初始化
  485.     for (string::size_type i = 1; i < sizeofMultiplicand; ++i)
  486.         bigInt[i] -= '0';
  487.       
  488.       
  489.     // 笔算乘法过程
  490.     for (string::size_type j = sizeofMultiplier - 1; j > 0; --j)
  491.     {
  492.         if (value.bigInt[j] > '0')
  493.         {
  494.             for (string::size_type k = sizeofMultiplicand - 1; k > 0; --k)
  495.                 product[k+j] += bigInt[k] * (value.bigInt[j] - '0');
  496.         }
  497.     }
  498.       
  499.     // 处理符号
  500.     if (bigInt[0] == value.bigInt[0])
  501.         product[0] = '+';
  502.     else
  503.         product[0] = '-';
  504.       
  505.     vector<unsigned int>::size_type sizeofProduct = product.size();
  506.     bigInt = string(sizeofProduct, '0');
  507.     bigInt[0] = product[0];
  508.       
  509.     // 处理进位问题
  510.     for (vector<unsigned int>::size_type n = sizeofProduct - 1; n > 1; --n)
  511.     {
  512.         product[n-1] += product[n] / 10;
  513.         product[n] %= 10;
  514.         bigInt[n] += product[n];
  515.     }
  516.       
  517.     if (product[1] == 0)
  518.         bigInt.erase(1, 1);
  519.     else
  520.         bigInt[1] += product[1];
  521.       
  522.     return *this;
  523. }
  524.   
  525. // 重复做差法求商
  526. CBigInt& CBigInt::operator /= (const CBigInt &value)
  527. {
  528.     // 除数为0
  529.     if (value.bigInt == "+0")
  530.     {
  531.         bigInt = "*Error!";
  532.         return *this;
  533.     }
  534.       
  535.     // 被除数大于除数
  536.     if (value.smaller(bigInt) == true)
  537.     {
  538.         string::size_type sizeofDividend = bigInt.size();
  539.         string::size_type sizeofDivisor = value.bigInt.size();
  540.         string answer(sizeofDividend, '0');
  541.           
  542.         // 符号处理
  543.         if (bigInt[0] == value.bigInt[0])
  544.             answer[0] = '+';
  545.         else
  546.             answer[0] = '-';
  547.           
  548.         string::size_type start = 1;
  549.         string::size_type end = sizeofDivisor - 1;
  550.           
  551.         while (end < sizeofDividend)
  552.         {
  553.             // 试商过程，从高位到低位
  554.             while (value.greater(bigInt.substr(start - 1, end - start + 2)) ==
  555.   
  556. false)
  557.             {
  558.                 string::size_type j = end;
  559.                 // 减法过程
  560.                 for (string::size_type i = sizeofDivisor - 1; i > 0; i--, j--)
  561.                 {
  562.                     bigInt[j] -= value.bigInt[i] - '0';
  563.                     if (bigInt[j] < '0')
  564.                     {
  565.                         bigInt[j] += 10;
  566.                         --bigInt[j-1];
  567.                     }
  568.                 }
  569.                   
  570.                 // 商的相应位加1
  571.                 ++answer[end];
  572.                   
  573.                 // 以除数做边界去掉前缀0
  574.                 while (start <= end && bigInt[start] == '0')
  575.                     ++start;
  576.             }
  577.               
  578.             // 以被除数做边界去掉前缀0
  579.             while (start < sizeofDividend && bigInt[start] == '0')
  580.                 ++start;
  581.               
  582.             // 如果end-start+1 < sizeofDivisor - 1,则进行补位
  583.             if (end - start + 2 < sizeofDivisor)
  584.                 end = sizeofDivisor + start - 2;
  585.             else
  586.                 ++end;
  587.         }
  588.         start = 1;
  589.         for (; start < answer.size() - 1 && answer[start] == '0'; ++start);
  590.         if (start > 1)
  591.             answer.erase(1, start - 1);
  592.   
  593.         bigInt = answer;
  594.     }
  595.     // 绝对值相等的情况
  596.     else if (value.equal(bigInt) == true)
  597.     {
  598.         string answer = "-1";
  599.         if (bigInt[0] == value.bigInt[0])
  600.             answer = "+1";
  601.         bigInt = answer;
  602.     }
  603.     else
  604.         bigInt = "+0";
  605.   
  606.     return *this;
  607. }
  608.   
  609. // 求余，与上面去商过程基本一致
  610. CBigInt& CBigInt::operator %= (const CBigInt &value)
  611. {
  612.     if (value.bigInt == "+0")
  613.     {
  614.         bigInt = "*Error!";
  615.         return *this;
  616.     }
  617.   
  618.     // 求余，余数为剩余bigInt值
  619.     if (value.smaller(bigInt) == true)
  620.     {
  621.         string::size_type sizeofDivident = bigInt.size();
  622.         string::size_type sizeofDivisor = value.bigInt.size();
  623.   
  624.         string::size_type start = 1;
  625.         string::size_type end = sizeofDivisor - 1;
  626.         while (end < sizeofDivident)
  627.         {
  628.             // 除数的值不大于被除数的值
  629.             while (value.greater(bigInt.substr(start - 1, end - start + 2)) ==
  630.   
  631. false)
  632.             {
  633.                 string::size_type j = end;
  634.                 for (string::size_type i = sizeofDivisor - 1; i > 0; --i, --j)
  635.                 {
  636.                     bigInt[j] -= value.bigInt[i] - '0';
  637.                     if (bigInt[j] < '0')
  638.                     {
  639.                         bigInt[j] += 10;
  640.                         --bigInt[j-1];
  641.                     }
  642.                 }
  643.   
  644.                 while (start <= end && bigInt[start] == '0')
  645.                     ++start;
  646.             }
  647.   
  648.             while (start < sizeofDivident && bigInt[start] == '0')
  649.                 ++start;
  650.   
  651.             if (end - start + 2 < sizeofDivisor)
  652.                 end = sizeofDivisor + start - 2;
  653.             else
  654.                 ++end;
  655.         }
  656.   
  657.         start = 1;
  658.         for (; start < sizeofDivident - 1 && bigInt[start] == '0'; start++);
  659.   
  660.         if (start > 1)
  661.             bigInt.erase(1, start - 1);
  662.   
  663.         if (bigInt == "-0")
  664.             bigInt[0] = '+';
  665.     }
  666.     else if (value.equal(bigInt))
  667.         bigInt = "+0";
  668.     return *this;
  669. }
  670.   
  671. CBigInt operator * (const CBigInt &lValue, const CBigInt &rValue)
  672. {
  673.     CBigInt product(lValue);
  674.     product *= rValue;
  675.     return product;
  676. }
  677.   
  678. CBigInt operator / (const CBigInt &lValue, const CBigInt &rValue)
  679. {
  680.     CBigInt quotient(lValue);
  681.     quotient /= rValue;
  682.     return quotient;
  683. }
  684.   
  685. CBigInt operator % (const CBigInt &lValue, const CBigInt &rValue)
  686. {
  687.     CBigInt mod(lValue);
  688.     mod %= rValue;
  689.     return mod;
  690. }
    说明：此次的判断字符串是否包含问题，来自一位外国网友提供的gofish、google面试题，这个题目出自此篇文章：http://www.aqee.net/2011/04/11/google-interviewing-story/，文章记录了整个面试的过程，比较有趣，值得一读。

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



                














    




    
  
    
阅读(1235) | 评论(0) | 转发(0) |
0

上一篇：linux进程间的通信(C)：信号

下一篇：查找出现M次的最长的字符串

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6