前奏
前一章，請見這：程序員面試題狂想曲：第一章、左旋轉字符串。本章裡出現的所有代碼及所有思路的實現，在此之前，整個網上都是沒有的。
文中的思路，聰明點點的都能想到，巧的思路，大師也已奉獻了。如果你有更好的思路，歡迎提供。如果你對此狂想曲系列有任何建議，歡迎微博上交流或來信指導。任何人，有任何問題，歡迎隨時不吝指正。
如果此狂想曲系列對你有所幫助，我會非常之高興，並將讓我有了永久堅持寫下去的動力。謝謝。
第一節、一道倆個字符串是否包含的問題
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;
}
上述代碼的時間復雜度為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)
{
if (lo < hi)
{
int k = partition(str, lo, hi);
quicksort(str, lo, k - 1);
quicksort(str, k + 1, hi);
}
}
//比較，上述排序O(m log m) + O(n log n)，加上下面的O(m+n)，
//時間復雜度總計為：O(mlogm)+O(nlogn)+O(m+n)。
void compare(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不可以自增。
//多謝helloword指正。
posTwo++;
}
if (posTwo == str2.length())
cout << "t
