字符串的包含

问题描述： 给定一个长字符串a和一个短字符串b。请问，如何最快地判断出短字符串b中的所有字符都在长字符串a中？请编写函数bool StringContain(string &a, string &b)实现此功能。为简单起见，假设输入的字符串只包含大写英文字母。

下面举几个例子：

 

（1）如果字符串a是"ABCD"，字符串b是"BAD"，答案是true，因为字符串b中的字母都在字符串a中，或者说b是a的真子集。

（2）如果字符串a是"ABCD"，字符串b是"BCE"，答案是false，因为字符串b中的字母E不在字符串a中。

（3）如果字符串a是"ABCD"，字符串b是"AA"，答案是true，因为字符串b中的字母A包含在字符串a中。

解题思路：

1.最直接的办法，蛮力轮询。对于这种方法，如果长字符串a的长度为n，短字符串b的长度为m，那么此算法需要比较次数为O(n*m)。显然该方法时间开销很大。

2.排序后轮询，根据题目只包括大写的英文字母，对两个字符串分别进行排序需要操作：O(mlogm)+O(nlogn),之后进行线性扫描需要O(n+m)

参考代码：

#include <bits/stdc++.h>

using namespace std;

bool StringContain( string &a , string &b )
{
    sort( a.begin() , a.end() );
    sort( b.begin() , b.end() );
int lena = a.length();
int lenb = b.length();
for(int pa = 0 , pb = 0 ; pb < lenb ; )
    {
while((pa < lena) && (a[pa] < b[pb]))
        {
++pa;
        }
if((pa >= lena) || (a[pa] > b[pb]))
        {
return false;
        }
++pb;
    }
return true;
}
int main()
{
string a  = "ABCD";
string b[3];
    b[0] = "BAD";
    b[1] = "BCE";
    b[2] = "AA";
for(int i=0;i<3;i++)
    {
if(StringContain(a,b[i]))
            cout<<a<<"  contains  "<<b[i]<<endl;
else
            cout<<a<<"  don't contain  "<<b[i]<<endl;
    }
return 0;
}

GCC运行结果：

3.位运算法。

将长字符串a的所有字符都存放在一个散列表(hash table)中，然后轮询短字符串b，看b中的每一个字符是否都在散列表中，若果都在则返回true，否则返回false

可以用位运算（26位整数表示）给相应的长字符串a就算出一个相对应的"签名",然后将字符串b的每一个字符都放在a中进行查找。

参考代码：

#include <bits/stdc++.h>

using namespace std;

bool StringContain( string &a , string &b )
{
int hash = 0;
int lena = a.length();
int lenb = b.length();
for( int i = 0 ; i < lena ; i++)
    {
        hash |= (1 << (a[i] - 'A'));
    }
for(int i = 0; i < lenb ; i++)
    {
if( ( hash & ( 1 << ( b[i] - 'A' ) ) ) == 0)
return false;
    }
return true;
}
int main()
{
string a  = "ABCD";
string b[3];
    b[0] = "BAD";
    b[1] = "BCE";
    b[2] = "AA";
for(int i=0;i<3;i++)
    {
if(StringContain(a,b[i]))
            cout<<a<<"  contains  "<<b[i]<<endl;
else
            cout<<a<<"  don't contain  "<<b[i]<<endl;
    }
return 0;
}

GCC运行结果：

该算法的空间复杂度为O(1)，时间复杂度为O(n+m)。