程序员编程艺术：第二章、字符串是否包含问题
作者：July，yansha，caopengcs。时间：二零一一年四月二十三日。致谢：老梦，nossiac，Hession，Oliver，luuillu，啊菜，雨翔，及微软100题实现小组所有成员。
题目描述：假设这有一个各种字母组成的字符串A，和另外一个字符串B，字符串里B的字母数相对少一些。什么方法能最快的查出所有小字符串B里的字母在大字符串A里都有？
比如，如果是下面两个字符串：String 1: ABCDEFGHLMNOPQRSString 2: DCGSRQPO答案是true，所有在string2里的字母string1也都有。 如果是下面两个字符串：String 1: ABCDEFGHLMNOPQRS String 2: DCGSRQPZ 答案是false，因为第二个字符串里的Z字母不在第一个字符串里。
点评： 1、题目描述虽长，但题意简单明了，就是给定一长一短的俩个字符串A，，B，假设A长B短，现在，要你判断B是否包含在字符串A中，即B?(-A。
2、题意虽简单，但实现起来并不轻松，且当如果面试官步步紧逼，一个一个否决你能想到的方法，要你给出更好、最好的方案时，你恐怕就要伤不少脑筋了。
ok，在继续往下阅读之前，您最好先想个几分钟，看你能想到的最好方案是什么，是否与本文最后实现的方法一致。
1.1、O（n*m）的轮询方法
判断string2中的字符是否在string1中?：String 1: ABCDEFGHLMNOPQRSString 2: DCGSRQPO
判断一个字符串是否在另一个字符串中，最直观也是最简单的思路是，针对第二个字符串string2中每一个字符，一一与第一个字符串string1中每个字符依次轮询比较，看它是否在第一个字符串string1中。
代码可如下编写：
//copyright@啊菜 2011//updated@July&Image丶时光 2013#include <iostream> #include <string>using namespace std; int CompareString(string LongString,string ShortString) { int i,j;for (i=0; i<ShortString.length(); i++) {for (j=0; j<LongString.length(); j++) //O(n*m){if (LongString[j] == ShortString[i]) //一一比较{break;}}if (j==LongString.length()){cout << "false" << endl;return 0;} } cout << "true" << endl; return 1; } int main() {string LongString="ABCDEFGHLMNOPQRS"; string ShortString="DCGSRQPO"; CompareString(LongString,ShortString); return 0; }
假设n是字符串string1的长度，m是字符串string2的长度，那么此算法，需要O（n*m）次操作，拿上面的例子来说，最坏的情况下将会有16*8 = 128次操作。显然，时间开销太大，我们需要找到一种更好的办法。
1.2、O(mlogm)+O(nlogn)+O(m+n)的排序方法 一个稍微好一点的方案是先对这两个字符串的字母进行排序，然后同时对两个字串依次轮询。两个字串的排序需要(常规情况)O(m log m) + O(n log n)次操作，之后的线性扫描需要O(m+n)次操作。
同样拿上面的字串做例子，将会需要16*4 + 8*3 = 88，再加上对两个字串线性扫描的16 + 8 = 24的操作。(随着字串长度的增长，你会发现这个算法的效果会越来越好)
关于采用何种排序方法，我们采用最常用的快速排序，下面的快速排序的代码用的是以前写的，比较好懂，并且，我执意不用库函数的qsort代码。唯一的问题是，此前写的代码是针对整数进行排序的，不过，难不倒我们，稍微改一下参数，即可，如下：
1.3、O（n+m）的计数排序方法
此方案与上述思路相比，就是在排序的时候采用线性时间的计数排序方法，排序O（n+m），线性扫描O（n+m），总计时间复杂度为：O（n+m）+O（n+m）=O（n+m）。
代码如下：
不过上述方法，空间复杂度为O（n+m），即消耗了一定的空间。有没有在线性时间，且空间复杂度较小的方案列?
第二节、寻求线性时间的解法2.1、O（n+m）的hashtable的方法 上述方案中，较好的方法是先对字符串进行排序，然后再线性扫描，总的时间复杂度已经优化到了：O（m+n），貌似到了极限，还有没有更好的办法列?
我们可以对短字串进行轮询（此思路的叙述可能与网上的一些叙述有出入，因为我们最好是应该把短的先存储，那样，会降低题目的时间复杂度），把其中的每个字母都放入一个Hashtable里(我们始终设m为短字符串的长度，那么此项操作成本是O(m)或8次操作)。然后轮询长字符串，在Hashtable里查询短字符串的每个字符，看能否找到。如果找不到，说明没有匹配成功，轮询长字符串将消耗掉16次操作，这样两项操作加起来一共只有8+16=24次。 当然，理想情况是如果长字串的前缀就为短字串，只需消耗8次操作，这样总共只需8+8=16次。
或如梦想天窗所说： 我之前用散列表做过一次，算法如下：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 or 扫描结束，退出循环。
代码实现，也不难，如下：
2.2、O（n+m）的数组存储方法
有两个字符串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。
黑夜下，撕开那张面具尽是怠倦的容颜，
