程序员面试题狂想曲：第二章、字符串是否包含
作者：July，yansha。
时间：二零一一年四月二十三日。
致谢：老梦，Hession，啊菜，及微软100题实现小组所有成员。
微博：http://weibo.com/julyweibo。
出处：http://blog.csdn.net/v_JULY_v。
-------------------------------------------
目录
曲之前奏
第一节、一道俩个字符串是否包含的问题
1.1、O（n*m）的轮询方法
1.2、O(mlogm)+O(nlogn)+O(m+n)的排序方法
1.3、O（n+m）的计数排序方法
第二节
2.1、O（n+m）的hashtable的方法
2.2、O（n+m）的数组存储方法
第三节、O（n）到O（n+m）的素数方法
前奏
本文章里出现的所有代码，在此之前，整个网上都是没有的。即，网上可能存在文章里的某些思路，但本文中的任何一行代码，都是本人和朋友yansha，以及微软100题实现组部分成员的劳动成果，希望，能得到您的尊重。
今上午想过一个问题，就是如果某一个人在面试一家公司时，正巧遇到了与本博客中相同的一道面试题目（我个人认为，此极为可能），然后，如果这个人可能当时情绪有点紧张，自己的思维一下子混乱了，于是他照搬了本博客中的思路，copy了本博客上的代码，最后，他通过了面试。
如果是本人面试，我会坦诚的说出我见过那到面试题。不过，我对他仍然表示恭喜，除此之外，便是，如果你因为本人的博客，对您的面试或找工作起到了一定的帮助，欢迎与我分享。
我会非常之高兴，并将让我有了永久坚持写下去的动力。谢谢。
第一节、一道俩个字符串是否包含的问题
1.0、题目描述：
假设这有一个各种字母组成的字符串，假设这还有另外一个字符串，而且这个字符串里的字母数相对少一些。从算法是讲，什么方法能最快的查出所有小字符串里的字母在大字符串里都有？
比如，如果是下面两个字符串：
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOM
答案是true，所有在string2里的字母string1也都有。
如果是下面两个字符串：
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOZ
答案是false，因为第二个字符串里的Z字母不在第一个字符串里。
点评：
1、题目描述虽长，但题意简单明了，就是给定一长一短的俩个字符串A，B，假设A长B短，现在，要你判断B是否包含在字符串A中，即B?(-A。
2、题意虽简单，但实现起来并不轻松，且当如果面试官步步紧逼，一个一个否决你能想到的方法，要你给出更好、最好的方案时，你恐怕就要伤不少脑筋了。
ok，在继续往下阅读之前，您最好先想个几分钟，看你能想到的最好方案是什么，是否与本文最后实现的方法一致。
1.1、O（n*m）的轮询方法
判断string2中的字符是否在string1中?：
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOM
判断一个字符串是否在另一个字符串中，最直观也是最简单的思路是，针对第二个字符串string2中每一个字符，一一与第一个字符串string1中每个字符依次轮询比较，看它是否在第一个字符串string1中。
假设n是字符串string1的长度，m是字符串string2的长度，那么此算法，需要O（n*m）次操作，拿上面的例子来说，最坏的情况下将会有16*8 = 128次操作。
我们不难写出以下代码：view plaincopy to clipboardprint?
#include <iostream>
using namespace std;
int compare(string str1,string str2)
{
for (int i=0; i<str2.length(); i++)
{
for (int j=0; j<str1.length(); j++) //O(n*m)
{
if (str2[i] == str1[j]) //一一比较
{
break;
}
}
if (j==str1.length())
{
cout << "false" << endl;
return 0;
}
}
cout << "true" << endl;
return 1;
}
int main()
{
string str1="ABCDEFGHLMNOPQRS";
string str2="DCGSRQPOM";
compare(str1,str2);
return 0;
}
#include <iostream>
using namespace std;
int compare(string str1,string str2)
{
for (int i=0; i<str2.length(); i++)
{
for (int j=0; j<str1.length(); j++) //O(n*m)
{
if (str2[i] == str1[j]) //一一比较
{
break;
}
}
if (j==str1.length())
{
cout << "false" << endl;
return 0;
}
}
cout << "true" << endl;
return 1;
}
int main()
{
string str1="ABCDEFGHLMNOPQRS";
string str2="DCGSRQPOM";
compare(str1,str2);
return 0;
}
上述代码的时间复杂度为O（n*m），显然，时间开销太大，我们需要找到一种更好的办法。
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代码。唯一的问题是，此前写的代码是针对整数进行排序的，不过，难不倒我们，稍微改一下参数，即可，如下：view plaincopy to clipboardprint?
//copyright@ 2011 July && yansha
//July，updated，2011.04.23.
#include <iostream>
#include <string>
using namespace std;
//以前的注释，还让它保留着
int partition(string &str,int lo,int hi)
{
int key = str[hi]; //以最后一个元素，data[hi]为主元
int i = lo - 1;
for(int j = lo; j < hi; j++) ///注，j从p指向的是r-1，不是r。
{
if(str[j] <= key)
{
i++;
swap(str[i], str[j]);
}
}
swap(str[i+1], str[hi]); //不能改为swap(&data[i+1],&key)
return i + 1;
}
//递归调用上述partition过程，完成排序。
void quicksort(string &str, int lo, int hi)
补充：综合编程 , 其他综合 ,
