程序员编程艺术：第二章、字符串是否包含及相关问题扩展

前奏

前一章，请见这：程序员面试题狂想曲：第一章、左旋转字符串。本章里出现的所有代码及所有思路的实现，在此之前，整个网上都是没有的。

文中的思路，聪明点点的都能想到，巧的思路，大师也已奉献了。如果你有更好的思路，欢迎提供。如果你对此狂想曲系列有任何建议，欢迎微博上交流或来信指导。任何人，有任何问题，欢迎随时不吝指正。

如果此狂想曲系列对你有所帮助，我会非常之高兴，并将让我有了永久坚持写下去的动力。谢谢。

第一节、一道俩个字符串是否包含的问题
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

补充：软件开发 , C语言 ,